阶乘后的零

每个末尾的 0,背后都藏着一对因子 2 和 5。问题就变成:n! 里 2 和 5 各有多少个?

2 多到用不完,5 才是稀缺资源。有几个 5,就能配几个 10,就有几个末尾 0。从此只数 5。

先用笨办法感受 · n = 25：把 1 到 25 里所有 5 的倍数挑出来(其它数不含因子 5)。下面逐个拆,看每个数里藏了几个 5。

5 = 5¹ · 贡献 1 个：5 本身就是 5,含 1 个因子 5。累计 1 个。

10 = 2×5 · 贡献 1 个：10 拆成 2×5,含 1 个 5。累计变 2。

15 = 3×5 · 贡献 1 个：15 = 3×5,又 1 个 5。累计 3。

20 = 4×5 · 贡献 1 个：20 = 4×5,再 1 个 5。累计 4。

25 = 5×5 · 贡献 2 个!：注意 25 = 5×5,它藏了 2 个因子 5!这一下累计跳到 6——这正是 25! 末尾有 6 个 0 的原因,也是这题的最大坑。

像 25 含两个 5:它在 n÷5 里被数过一次,再在 n÷25 里被补数一次,正好两次。下面用这个公式把 n=100 完整走一遍。

公式法 · n = 100 起步：下面这排是除数 d = 5 的各次幂。指针从 5 开始,每次算 100 ÷ d 加进答案,然后 d ×5 右移一格。

指针落在第 1 个除数：指针落到第一个除数 5。先看循环条件:5 ≤ 100 成立,可以进循环开始累加。

100 ÷ 5 = 20：100 ÷ 5 = 20(整数除法):1..100 里有 20 个数至少含一个 5。答案累加到 20。

d ×5 → 25 · 第 2 项：把除数 ×5 变成 25,指针右移一格。25 还 ≤ 100,要继续——这一步专门补数那些「含两个 5」的数(25、50、75、100)。

100 ÷ 25 = 4：100 ÷ 25 = 4:有 4 个数(25/50/75/100)含第二个 5,补上这 4 个。答案累加到 24。

d ×5 → 125 · 越界：除数再 ×5 变成 125,可 125 > 100 了,100 ÷ 125 = 0 没意义。后面的除数全用不上(变灰),循环停止。

n = 100 · 完成：用到的两项(绿色):100÷5=20 和 100÷25=4,相加 24。这就是 100! 末尾零的个数,全程没碰那个天文数字。

再用公式跑 · n = 25 起步：换回开头的 n = 25,答案归零重新开始,用公式再走一遍,看是否也得 6,和前面逐个拆的结果对上。

指针回到第 1 个除数：指针回到除数 5。5 ≤ 25 成立,开始累加。

25 ÷ 5 = 5：25 ÷ 5 = 5:5,10,15,20,25 这 5 个数各至少一个 5。答案累加到 5。

d ×5 → 25 · 第 2 项：除数 ×5 到 25,指针右移。25 ≤ 25 仍要算——这一步补数 25 里的第二个 5。

25 ÷ 25 = 1：25 ÷ 25 = 1:只有 25 这一个数含第二个 5,补上 1。答案 6——和前面逐个拆的结果完全一致!

d ×5 → 125 · 越界：除数到 125 已 > 25,停。最终 25! 末尾 6 个 0,公式法验证通过。

记住这个公式:不断除以 5 的更高次幂并累加,本质就是把每个含多个 5 的数分层数清。

雷区实演 · 只除一次会漏：假如只除一次就返回,n=25 会得 5,漏掉 25 里第二个 5。必须继续除 25、125…把多层的 5 都补上才对。

边界三连：先想最小(0/4 无 5 → 0)、再想含 5² 的(25),三种过一遍代码就稳。

面试追问：把「为何只数 5」「为何要分层除」「为何 O(log n)」讲清,是这题的得分点。