企业官网建设流程全解析

• 教程
• 文档
• 知识库

本篇技术指南基于「算法通关手册」仓库中的 0172. 阶乘后的零题解 展开，系统讲解如何利用数论中「因子分解」的思路，在 O(log n) 时间内求出n!末尾零的个数。读完本文，你将掌握「尾随零」类题目的统一解法模型，并理解它与仓库内 面试题 16.05. 阶乘尾数、0793. 阶乘函数后 K 个零 等同类题目的递进关系。

题目信息

• 题号：0172
• 题目：阶乘后的零（Factorial Trailing Zeroes）
• 标签：数学
• 难度：中等
• 题解文档：factorial-trailing-zeroes.md

题目大意

给定一个整数n，要求返回n!（即n的阶乘）结果中尾随零（trailing zeroes）的数量。

约束条件：

$$0 \le n \le 10^4$$

由于n最大可达10^4，n!是一个拥有数万个数字位的超长整数，任何「先算阶乘再数零」的直接做法都会面临溢出或大数计算开销过大的问题，因此必须从数学角度寻找规律。

核心数学原理：尾随零从何而来

在十进制中，一个数字每乘上10，末尾就会多一个0。而：

$$10 = 2 \times 5$$

因此，n!末尾零的个数，等价于1 × 2 × 3 × ... × n这个连乘结果中能组成多少个(2, 5)因子对。由于每一对2 × 5都能贡献一个因子10，所以：

尾随零的个数 = min(因子 2 的个数, 因子 5 的个数)

接下来是一个关键的观察：在从1到n的所有整数中，因子 2 的个数永远不少于因子 5 的个数。

为什么？因为偶数每隔2个就会出现一次（贡献一个2），而5的倍数每隔5个才出现一次。例如在1 ~ 10中：

直观上，由于2 < 5，在任意前缀1 ~ n中，「包含因子 2 的整数」出现得更频繁、更密集，累计贡献的2因子数量一定大于等于累计贡献的5因子数量。所以上式中的min恒等于因子 5 的个数。

于是原问题被转化为一个更简单的问题：

求n!中质因子5的总个数。

这也是整个题解（factorial-trailing-zeroes.md）的核心结论：「尾随 0 的个数为 2 的倍数个数和 5 的倍数个数的最小值，又因为 2 < 5，2 的倍数个数肯定小于等于 5 的倍数，所以直接统计 5 的倍数个数即可。」

统计公式：勒让德公式（Legendre's Formula）的阶乘版本

「统计n!中质因子5的总个数」听起来简单，但要小心一个陷阱：不仅仅是5的倍数在贡献因子 5。

以n = 25为例：

• 5, 10, 15, 20, 25是5的倍数，共5个，贡献 5 个因子5；
• 但其中25 = 5²本身含有两个因子 5，上述统计只算了 1 个，少算了 1 个。

因此需要一层一层地「剥洋葱」：

1. 先统计n以内所有5的倍数个数：⌊n / 5⌋；
2. 再统计所有25的倍数个数（它们额外多贡献一个 5）：⌊n / 25⌋；
3. 再统计所有125的倍数个数：⌊n / 125⌋；
4. 以此类推，直到5^k > n为止。

最终公式为：

$$f(n) = \left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{25} \right\rfloor + \left\lfloor \frac{n}{125} \right\rfloor + \cdots = \sum_{k=1}^{+\infty} \left\lfloor \frac{n}{5^k} \right\rfloor$$

这就是统计n!中某个质因子个数的通用公式（勒让德公式）。以n = 25验证：

$$f(25) = \lfloor 25/5 \rfloor + \lfloor 25/25 \rfloor + \lfloor 25/125 \rfloor = 5 + 1 + 0 = 6$$

而25! = 15511210043330985984000000，末尾确实有 6 个零，验证通过。

代码实现与逐行解析

仓库题解给出的 Python 实现如下（factorial-trailing-zeroes.md）：

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

这段代码将上面公式中的「每一层⌊n / 5^k⌋」压缩成了循环：

正确性推导：循环第 1 轮累加⌊n/5⌋，第 2 轮累加⌊n/25⌋，第 3 轮累加⌊n/125⌋……恰好逐项复现公式，直到某轮n < 5后所有项均为 0 而退出，与公式完全等价。

边界情况：

• n = 0：0! = 1，末尾没有零，循环体不执行，返回0，正确；
• n = 1 ~ 4：阶乘值分别为1, 2, 6, 24，均无尾随零，n // 5 = 0，返回0，正确；
• n = 5：5! = 120，尾随零为 1；循环第 1 轮count = 1，n = 1；第 2 轮count = 1，n = 0；返回 1，正确。

复杂度分析

• 时间复杂度：$O(\log_5 n)$。每轮循环n除以5，循环次数为 $\log_5 n$ 量级。当n = 10^4时，仅需约 $\log_5 10^4 \approx 6$ 轮，几乎可以视为常数时间。
• 空间复杂度：$O(1)$。只使用了单个整数变量count，不依赖任何额外数据结构。

相比「直接计算n!再统计末尾零」的方案——其时间复杂度为 $O(n)$ 且需要处理超大整数——本解法在时间上是指数级的提升，同时彻底规避了溢出问题。

手动推演示例

用几个典型输入走一遍算法，加深理解：

示例 1：n = 10

10! = 3628800，尾随零为 2。

计算过程：⌊10/5⌋ + ⌊10/25⌋ = 2 + 0 = 2，正确。

示例 2：n = 100

100!的尾随零为 24。

计算过程：⌊100/5⌋ + ⌊100/25⌋ + ⌊100/125⌋ = 20 + 4 + 0 = 24，其中25, 50, 75, 100四个数各多贡献了一个 5，正确。

示例 3：n = 125

125 = 5³自身贡献了 3 个因子 5，因此结果31比「125 以内 5 的倍数个数 25」多出 6 个，全部来自25与125的更高次幂项，正确。

一题多解视角与同类题延伸

这道题的解法属于数学推导型题目，核心方法论可归纳为三步：

1. 建立映射：末尾零 → 因子 10 → 因子对(2, 5)；
2. 化简问题：利用2因子恒富余的性质，把问题转化为只统计5因子；
3. 逐层统计：用⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ...精确计数。

「算法通关手册」仓库中与该题直接相关的姊妹题目还有：

• 面试题 16.05. 阶乘尾数：题目要求与 0172 完全一致，被归入「面试题」系列，同样采用统计 5 的倍数个数的解法，可作为本题的镜像练习；
• 0793. 阶乘函数后 K 个零：困难难度，将本题的结论f(x)（x!末尾零个数）抽象成单调函数，再利用二分查找求解满足f(x) = k的x个数，是本题数学结论的高级应用。

这三道题在仓库中形成了「基础题 → 面试题 → 进阶题」的完整学习链路，均可通过题解汇总目录 docs/solutions/index.md 与 00_05_solutions_list.md 检索定位。

小结

LeetCode 0172「阶乘后的零」是一道经典的数论入门题，考察的核心能力是质因子分解与计数。它的关键结论——尾随零个数等于n!中因子 5 的个数——不仅能在 $O(\log n)$ 时间内直接给出答案，更是解决 0793「阶乘函数后 K 个零」等进阶问题的基础工具。建议读者在掌握本题后，继续完成仓库中 面试题 16.05 的独立编写，并尝试阅读 0793 题解 中二分查找与本题结论结合的设计思路，从而彻底吃透「尾随零」这一题型。

• 教程
• 文档
• 知识库