LeetCode 172. 阶乘后的零

◎

本节目标

将阶乘末尾零转换为质因数 5 的指数累加。

查看原题

返回数学建模框架

题意与约束

求 n! 十进制表示末尾连续零的数量，n 是非负整数。

第一反应与瓶颈

先计算阶乘再检查末尾零会快速溢出，即使使用大整数也浪费：末尾零只关心质因数分解中的一小部分。

数学关系与算法推导

每个零来自一对 2 × 5。阶乘中 2 的数量总多于 5，因此只统计 5：⌊n/5⌋ 统计至少一个 5，⌊n/25⌋ 补上第二个 5，依次累加到商为零。

正确性依据

一个数含有几个 5，就会在相应的 n / 5^k 项中被计数几次。所有 k ≥ 1 的计数恰好覆盖 1..n 中每个 5 的指数总和；每个 5 都能配对一个 2，故总数就是末尾零数。

样例执行过程

25! 中，25 / 5 = 5 给出五个 5，25 / 25 = 1 给出 25 额外的一个 5，因此答案是 6。

代码实现

C++

C++17

class Solution {
public:
    int trailingZeroes(int n) {
        int count = 0;
        while (n > 0) {
            n /= 5;
            count += n;
        }
        return count;
    }
};

Python

Python 3

class Solution:
    def trailingZeroes(self, n: int) -> int:
        count = 0
        while n > 0:
            n //= 5
            count += n
        return count

复杂度分析

• 时间复杂度：O(log_5 n)。
• 空间复杂度：O(1)。

边界与易错点

• 0! = 1，答案为 0。
• 不能只返回 n / 5，25、125 会贡献额外的 5。
• 循环里先除以 5 再累加，避免重复计入当前商。

模式迁移

当题目问乘积末尾性质、整除次数或质因数总指数时，优先把对象拆为各个因子的贡献，而非真的构造乘积。