中–难 · 技巧在算术
阶乘末尾零
输入大到算不出来。这不是题目的缺陷 —— 这是题目在告诉你:答案不在计算里。
一句话答案末尾的 0 来自因子 5，所以答案是 n/5 + n/25 + n/125 + … —— 千万不要去算 n!，n 到 10⁹ 时那个数大得离谱。
题目
输入: 一个整数 n(1 ≤ n ≤ 1,000,000,000)。
输出: n! 末尾有多少个零,其中 n! = 1 × 2 × … × n。
样例:
| 输入 | 输出 |
|---|---|
5 | 1 |
10 | 2 |
25 | 6 |
10! = 3628800 → 两个零。25! = 15511210043330985984000000 → 六个。注意 25/5 只有 5 —— 第六个零来自 25 贡献了两个 5 的因子。
你的解答
「运行我的输入」用的自定义输入
判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。
卡住了？提示
提示 1 — 一个末尾零就是一个 10 的因子
每一个末尾零都意味着这个数又能被一个 10 整除,而 10 = 2 × 5。于是问题变成:n! 里藏了多少对 (2, 5)?因为偶数远比 5 的倍数多,所以 5 的个数才是瓶颈 —— 数 5 就行了。
提示 2 — 不是 n/5 —— 那正是陷阱
n / 5 只数了 5 的倍数,但 25 贡献两个 5、125 贡献三个,依此类推。再加上 n / 25、n / 125,一直加下去。循环短得漂亮:while (n > 0) { n /= 5; zeros += n; } —— 直接除 n 自己并累加。
提示 3 — 为什么绝不能从 1 循环到 n
从 1 乘到 1,000,000,000 是 109 次迭代,而且这个数本身早就溢出所有整数类型了。就算不溢出,标签页也会卡死。当输入范围让暴力不可能时,这本身就是个提示:正解是 O(log n) 或 O(1)。
题解（先自己试试！）
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long zeros = 0;
while (n > 0) {
n = n / 5;
zeros = zeros + n;
}
cout << zeros << endl;
return 0;
}这是闯关链的最后一题,也很合适:没有数组、没有遍历输入、没有递归 —— 只有一个观察,把十亿次乘法换成了十几次除法。这就是「会写程序」和「会编程」的区别:后者看得出这道题从头到尾问的都不是阶乘。回到题库列表,数数现在有多少道你能不看提示做出来。
深度解析
为什么这样做对
每个末尾零都是一个 10 的因子,而 10 = 2 × 5。偶数远比 5 的倍数多,所以 5 才是瓶颈 —— 数 5。
代价
O(log_5 n):十亿也只要 12 次除法。而从 1 乘到 n 是 10^9 次乘法,那个数还早就溢出了。
常见错法
- 只算
n / 5:漏掉 25 贡献的第二个 5、125 贡献的第三个。n = 25 时就已经少算一个。 - 试图真的算 n!:输入到十亿时既溢出所有整数类型,又会卡死标签页。输入范围让暴力不可能,这本身就是提示。
下一步
闯关到这里结束。回到 第一题 看看你走了多远。
记住这两句
- 末尾零 = 2×5 的对数,而 5 是稀缺的那一边。
n / 5不够,还要加n / 25、n / 125……
🐞 这段是错的 —— 点开,亲手让它挂一次
只算了 n / 5 —— 漏掉 25、125、625 贡献的额外 5
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long zeros = n / 5;
cout << zeros << endl;
return 0;
}