阶乘后有多少个尾随零？（LeetCode 172）

简化版

求 n!（n 的阶乘）末尾有多少个 0。末尾的 0 来自因子 10 = 2 × 5，而在 1×2×…×n 里因子 2 远多于因子 5，所以尾零个数 = n! 中因子 5 的个数。做法是统计 1 到 n 里所有数贡献的因子 5：n/5 + n/25 + n/125 + ...（25 贡献两个 5、125 贡献三个……）。用循环 count += n / 5^k 直到 5^k > n，O(log n) 完成，不用真算阶乘。

详细版

int trailingZeroes(int n) {
    int count = 0;
    for (long pow = 5; pow <= n; pow *= 5) {   // pow = 5, 25, 125, ...
        count += n / pow;                       // 累加 n 中含该 5 的幂的个数
    }
    return count;
}

等价写法（不断除 5）：

int trailingZeroes(int n) {
    int count = 0;
    while (n > 0) {
        n /= 5;
        count += n;      // 累加 n/5 + n/25 + n/125 + ...
    }
    return count;
}

尾零来自 10 = 2×5，而 2 的因子远多于 5，所以尾零数 = 因子 5 的个数。
n/5 + n/25 + n/125 + ...：5 的倍数各贡献一个 5，25 的倍数额外再贡献一个，依此类推。
复杂度：O(log₅ n)。不需要计算阶乘本身（会溢出）。

完整版教学

一、尾零从哪来：因子 10 = 2 × 5

一个数末尾的 0 的个数，等于它含有多少个因子 10。而 10 = 2 × 5，所以每一对 (2, 5) 因子产生一个尾零。对于 n! = 1 × 2 × 3 × … × n，要数它末尾有几个 0，就是数它的质因数分解里能凑出多少对 (2, 5)——也就是 min(因子 2 的个数, 因子 5 的个数)。

二、关键：因子 5 才是瓶颈

在 1×2×…×n 中，因子 2 出现的次数远多于因子 5——因为每隔 2 个数就有一个偶数（贡献 2），而每隔 5 个数才有一个 5 的倍数（贡献 5）。所以 2 总是「过剩」，能配成多少对 (2,5) 完全取决于因子 5 的个数。于是：

尾零个数 = n! 中因子 5 的个数

问题转化为「统计 1 到 n 的所有数里，一共含有多少个质因子 5」。

三、怎么数因子 5：n/5 + n/25 + n/125 + …

统计 1 到 n 中因子 5 的总数，要分层考虑：

5 的倍数（5, 10, 15, 20, 25, …）：每个至少贡献一个 5，共 ⌊n/5⌋ 个。
25 的倍数（25, 50, 75, …）：每个含有两个 5（25 = 5×5），前面 n/5 只数了它一个，要再加一个，共 ⌊n/25⌋ 个额外的 5。
125 的倍数：含三个 5，再加 ⌊n/125⌋……
依此类推，直到 5^k > n。

所以总数 = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …。例：n = 100：100/5 + 100/25 = 20 + 4 = 24（100/125=0 停止）。所以 100! 末尾有 24 个 0。

四、两种等价实现

写法一（累加 5 的幂）：pow 从 5 开始每次 ×5，累加 n / pow，直到 pow > n。注意 pow 用 long，防止 pow *= 5 溢出 int。
写法二（不断除 5）：while (n > 0) { n /= 5; count += n; }。每次 n /= 5 相当于依次得到 n/5, n/25, n/125…，累加即可。这个写法更简洁、无溢出风险，推荐。

两者数学上等价，都是 O(log₅ n)。

五、为什么不能直接算 n!

有人想「先算出 n! 再数末尾 0」——不可行。n! 增长极快，21! 就超过 long 范围，n 稍大就溢出，根本存不下。本题的精妙就在于绕开阶乘本身，直接从质因数角度 O(log n) 求解。这也是数论题的常见套路：不硬算大数，而是分析其因子结构。

六、分层计数避免漏掉多个因子 5

floor(n/5) 先给每个 5 的倍数贡献一个因子 5；floor(n/25) 再给 25 的倍数补第二个；后续 125、625 同理。分层相加恰好等于每个整数中 5 的指数之和，不会重复计错，因为每一层代表“至少还有第 k 个 5”。

n=30
floor(30/5)=6：5,10,15,20,25,30 各贡献一个 5
floor(30/25)=1：25 再额外贡献一个 5
floor(30/125)=0：停止
总因子 5 数量 6+1=7
30! 尾随零为 7
其中 25 贡献两个零所需的两个 5

校验维度	本题必须保持的结论
循环/递推不变量	第 k 轮累加所有至少含 k 个因子 5 的数，除法后 n 严格缩小。
边界条件	`n<5` 返回 0；循环乘 `divisor*=5` 可能溢出，反复 `n/=5` 更稳。
复杂度与代价	除数按 5 倍增长，时间 O(log₅n)，空间 O(1)，无需构造阶乘。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

数学题不能只凭样例相信公式，必须同时核对定义域、推导条件和定宽整数边界。本题应先复述这条不变量：第 k 轮累加所有至少含 k 个因子 5 的数，除法后 n 严格缩小。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“n=30”开始手推，最后应得到“其中 25 贡献两个零所需的两个 5”。
边界复核：n<5 返回 0；循环乘 divisor*=5 可能溢出，反复 n/=5 更稳。
代价复核：除数按 5 倍增长，时间 O(log₅n)，空间 O(1)，无需构造阶乘。
用 0、1、最小合法值和最大合法值检查公式的定义域。
乘法、取绝对值或取负前先判断是否可能触及 Integer.MIN_VALUE 等不对称边界。
若算法依赖单调性、抵消或整除关系，要明确题设保证何时成立、何时必须额外验证。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“第 k 轮累加所有至少含 k 个因子 5 的数，除法后 n 严格缩小。”这条正确性主线不能省。

八、常见误区与追问

误区：答案就是 n/10。 尾零由阶乘中因子配对决定，不是每十个整数固定产生一个。
误区：只计算 n/5 已经足够。 25、125 等含多个因子 5，必须继续分层补计。
误区：因子 2 和因子 5 都要完整统计。 阶乘中偶数远多于 5 的倍数，2 一定充足，瓶颈是 5。
追问：100! 有多少个尾零？ 100/5+100/25=20+4=24，下一层为 0。
追问：为什么不能先算 n! 再数零？ 阶乘增长极快会溢出，而且计算了与答案无关的巨大数值。
追问：其他进制的尾零如何求？ 分解进制基数的质因子，统计各质因子指数后按所需幂次取最小配对数。

九、加强记忆

阶乘尾零个数 = n! 中因子 5 的个数。因为尾零来自 10 = 2×5，而 1×2×…×n 里因子 2 远多于 5，配对数由 5 决定。统计因子 5：⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …（5 的倍数各贡献一个、25 的倍数再加一个……）。简洁写法 while(n>0){ n/=5; count+=n; }，O(log₅ n)。绝不要真算 n!（会溢出），直接分析因子。核心一句：尾零看因子 5，一路除 5 累加。

简化版

详细版