这是一个经典的数论问题。以下是针对该题目的简洁解析和 C++ 代码。
解题思路
-
核心原理：
阶乘末尾的
0是由因子 \(2\) 和 \(5\) 相乘得到的（\(2 \times 5 = 10\)）。 -
瓶颈因素：
在 \(1\) 到 \(n\) 的乘积中，因子 \(2\) 的数量远远多于因子 \(5\) 的数量。因此，末尾 \(0\) 的个数完全取决于因子 \(5\) 的个数。
-
计算方法：
我们需要计算 \(n!\) 中包含多少个因子 \(5\)。
- \(n\) 除以 \(5\)，得到包含至少 \(1\) 个因子 \(5\) 的数的个数。
- \(n\) 除以 \(25\)（\(5^2\)），得到包含至少 \(2\) 个因子 \(5\) 的数的个数。
- 以此类推，不断除以 \(5\) 并累加商，直到 \(n\) 为 \(0\)。
公式为：\(ans = \lfloor \frac{n}{5} \rfloor + \lfloor \frac{n}{25} \rfloor + \lfloor \frac{n}{125} \rfloor + \dots\)
C++ 代码实现
#include <iostream>using namespace std;int main() {// 题目数据范围 n < 2*10^9，int (约21亿) 刚好够用，// 但习惯上建议使用 long long 防止边界溢出或便于后续扩展。long long n;cin >> n;long long ans = 0;// 循环不断除以 5while (n > 0) {ans += n / 5; // 累加当前的商n /= 5; // 更新 n}cout << ans << endl;return 0;
}
复杂度分析
- 时间复杂度：\(O(\log_5 n)\)。因为每次 \(n\) 都缩小 \(5\) 倍，计算非常快，对于 \(2 \times 10^9\) 的数据也能瞬间完成。
- 空间复杂度：\(O(1)\)。只需要常数级变量。
示例推演 (n=100)
- \(100 / 5 = 20\)
- \(20 / 5 = 4\)
- \(4 / 5 = 0\) (结束)
- 答案：\(20 + 4 = 24\) 个 \(0\)。