时间轴

2025-11-26

init

题目：

P172 阶乘后的零

https://leetcode.cn/problems/factorial-trailing-zeroes/description/?envType=study-plan-v2&envId=top-interview-150

10 是由 2 × 5 组成的，而阶乘 n! 中 2 的数量永远更多，造成 5 成为短板。尾零是因为结尾有：

所以 n! 有多少个尾零，就取决于 有多少对 (2, 5)。但在 n! 里：

  • 偶数很多 → 2 的因子数目超多
  • 能提供 5 的数却很少（只有 5、10、15、20、25 …）

因为含有 5 的数的分布是：

  • 每 5 个数出现 1 个含一个 5（如 5,10,15,20）
  • 每 25 个数出现 1 个含“额外的 5”（如 25,50,75）
  • 每 125 个出现含“再多一个 5”，等等
    …
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public:
	int trailingZeroes(int n)
	{
		int cnt = 0;
		while (n > 0) {
			n /= 5;
			cnt += n;
		}
		return cnt;
	}
};