当前位置：首页 > news >正文

UVa 12630 Equilateral Triangle in a Grid

news 2026/6/30 4:13:13

题目翻译

在一个等边三角形中，每条边上有nnn个均匀分布的“点”，这些点构成了一个三角形点阵。下图展示了n=4n=4n=4时的点阵示例。

问题：
在这个点阵中，有多少个不同的等边三角形？要求每个等边三角形的顶点必须是点阵中的点。

注意：
等边三角形有多种大小和方向。

输入格式：
输入包含多行，每行一个整数nnn(2≤n≤100)(2 \leq n \leq 100)(2≤n≤100)，表示每条边上的点数。输入以一行单独的000结束。输入文件不超过202020行。

输出格式：
对于每个nnn，输出一行，表示在该点阵中可以找到的不同等边三角形的总数。

题目分析

本题要求计算在边长为nnn（每条边有nnn个点）的等边三角形点阵中，所有顶点落在格点上的等边三角形的数量。这些三角形可以有不同的边长和方向，不能遗漏。

关键观察

点阵结构
点阵共有n(n+1)2\frac{n(n+1)}{2}2n(n+1)个点，排列成一个正三角形。
等边三角形的可能方向
在正三角形网格中，等边三角形并不只有“一条边水平”这一种方向。实际上，由于网格具有60∘60^\circ60∘和120∘120^\circ120∘的对称性，存在多种方向的等边三角形。直接枚举所有方向并计数非常复杂。
组合数学方法
通过观察样例数据：
- 当n=2n=2n=2时，答案为111
- 当n=3n=3n=3时，答案为555
  我们可以猜测答案可能是一个关于nnn的多项式。

公式推导（结论）

经过数学推导（或查表OEIS A000332\texttt{OEIS A000332}OEIS A000332），可以发现：答案等于组合数(n+24)\binom{n+2}{4}(4n+2)。

即：
答案=(n+2)(n+1)n(n−1)24 \text{答案} = \frac{(n+2)(n+1)n(n-1)}{24}答案=24(n+2)(n+1)n(n−1)

为什么是这个公式？
一种经典解释是：在正三角形点阵中，每个等边三角形唯一对应一个由四个点确定的“外接平行四边形”（或通过某种投影映射到四个顶点），因此总数等于从n+2n+2n+2个“虚拟顶点”中选择444个的组合数。具体证明涉及对网格的坐标变换和计数，这里不做展开。

解题思路

读入nnn，直到遇到000为止。
对于每个nnn，直接使用公式计算：
answer=(n+2)×(n+1)×n×(n−1)24 \texttt{answer} = \frac{(n+2) \times (n+1) \times n \times (n-1)}{24}answer=24(n+2)×(n+1)×n×(n−1)
注意使用long long或int64_t避免乘法溢出。
输出结果。

时间复杂度：O(1)O(1)O(1)每询问。
空间复杂度：O(1)O(1)O(1)。

代码实现

// Equilateral Triangle in a Grid// UVa ID: 12630// Verdict: Accepted// Submission Date: 2025-12-17// UVa Run Time: 0.000s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;while(cin>>n&&n){// 公式：C(n+2, 4) = (n + 2) * (n + 1) * n * (n - 1) / 24longlonganswer=1LL*(n+2)*(n+1)*n*(n-1)/24;cout<<answer<<endl;}return0;}