企业官网建设流程全解析

题目翻译

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

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

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

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

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

题目分析

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

关键观察

1. 点阵结构
   点阵共有n(n+1)2\frac{n(n+1)}{2}2n(n+1)​个点，排列成一个正三角形。

2. 等边三角形的可能方向
   在正三角形网格中，等边三角形并不只有“一条边水平”这一种方向。实际上，由于网格具有60∘60^\circ60∘和120∘120^\circ120∘的对称性，存在多种方向的等边三角形。直接枚举所有方向并计数非常复杂。

3. 组合数学方法
   通过观察样例数据：

   • 当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个的组合数。具体证明涉及对网格的坐标变换和计数，这里不做展开。

解题思路

1. 读入nnn，直到遇到000为止。
2. 对于每个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避免乘法溢出。
3. 输出结果。

时间复杂度：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时不可行，因此必须依靠数学推导或已知结论。在竞赛中，如果遇到类似“正三角形网格中等边三角形计数”的问题，可以尝试使用这个公式。