题目翻译
在一个等边三角形中，每条边上有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;}样例验证
输入：
2 3 0输出：
1 5与题目样例一致。
总结
本题是一个经典的组合计数问题，关键在于找到隐藏的组合数公式(n+24)\binom{n+2}{4}(4n+2)。直接枚举所有三角形在n≤100n \leq 100n≤100时不可行，因此必须依靠数学推导或已知结论。在竞赛中，如果遇到类似“正三角形网格中等边三角形计数”的问题，可以尝试使用这个公式。
