教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇技术指南基于「算法通关手册」仓库中的 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^4n!是一个拥有数万个数字位的超长整数任何「先算阶乘再数零」的直接做法都会面临溢出或大数计算开销过大的问题因此必须从数学角度寻找规律。核心数学原理尾随零从何而来在十进制中一个数字每乘上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 的个数42²20550182³30102 × 511直观上由于2 5在任意前缀1 ~ n中「包含因子 2 的整数」出现得更频繁、更密集累计贡献的2因子数量一定大于等于累计贡献的5因子数量。所以上式中的min恒等于因子 5 的个数。于是原问题被转化为一个更简单的问题求n!中质因子5的总个数。这也是整个题解factorial-trailing-zeroes.md的核心结论「尾随 0 的个数为 2 的倍数个数和 5 的倍数个数的最小值又因为 2 52 的倍数个数肯定小于等于 5 的倍数所以直接统计 5 的倍数个数即可。」统计公式勒让德公式Legendres Formula的阶乘版本「统计n!中质因子5的总个数」听起来简单但要小心一个陷阱不仅仅是5的倍数在贡献因子 5。以n 25为例5, 10, 15, 20, 25是5的倍数共5个贡献 5 个因子5但其中25 5²本身含有两个因子 5上述统计只算了 1 个少算了 1 个。因此需要一层一层地「剥洋葱」先统计n以内所有5的倍数个数⌊n / 5⌋再统计所有25的倍数个数它们额外多贡献一个 5⌊n / 25⌋再统计所有125的倍数个数⌊n / 125⌋以此类推直到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_{k1}^{\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.mdclass Solution: def trailingZeroes(self, n: int) - int: count 0 while n 0: count n // 5 n n // 5 return count这段代码将上面公式中的「每一层⌊n / 5^k⌋」压缩成了循环行号操作作用3count 0初始化计数器4while n 0循环直到n 5此时⌊n / 5⌋ 0更高次幂项也为 0可以停止5count n // 5累加当前这一层5^k的倍数个数6n n // 5将n缩小 5 倍等价于进入下一层k 1正确性推导循环第 1 轮累加⌊n/5⌋第 2 轮累加⌊n/25⌋第 3 轮累加⌊n/125⌋……恰好逐项复现公式直到某轮n 5后所有项均为 0 而退出与公式完全等价。边界情况n 00! 1末尾没有零循环体不执行返回0正确n 1 ~ 4阶乘值分别为1, 2, 6, 24均无尾随零n // 5 0返回0正确n 55! 120尾随零为 1循环第 1 轮count 1n 1第 2 轮count 1n 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)$ 且需要处理超大整数——本解法在时间上是指数级的提升同时彻底规避了溢出问题。手动推演示例用几个典型输入走一遍算法加深理解示例 1n 1010! 3628800尾随零为 2。循环轮次当前 n累加值 n // 5累计 count第 1 轮1022第 2 轮202计算过程⌊10/5⌋ ⌊10/25⌋ 2 0 2正确。示例 2n 100100!的尾随零为 24。循环轮次当前 n累加值 n // 5累计 count第 1 轮1002020第 2 轮20424第 3 轮4024计算过程⌊100/5⌋ ⌊100/25⌋ ⌊100/125⌋ 20 4 0 24其中25, 50, 75, 100四个数各多贡献了一个 5正确。示例 3n 125循环轮次当前 n累加值 n // 5累计 count第 1 轮1252525第 2 轮25530第 3 轮5131第 4 轮1031125 5³自身贡献了 3 个因子 5因此结果31比「125 以内 5 的倍数个数 25」多出 6 个全部来自25与125的更高次幂项正确。一题多解视角与同类题延伸这道题的解法属于数学推导型题目核心方法论可归纳为三步建立映射末尾零 → 因子 10 → 因子对(2, 5)化简问题利用2因子恒富余的性质把问题转化为只统计5因子逐层统计用⌊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 题解 中二分查找与本题结论结合的设计思路从而彻底吃透「尾随零」这一题型。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 172 Factorial Trailing Zeroes 题解数论推导「阶乘后的零」的 O(log n) 解法LeetCode 172 Factorial Trailing Zeroes 题解数论推导「阶乘后的零」的 O log n 解法 本篇技术指南以 leetco文档教程知识库LeetCode 172 阶乘后的零Factorial Trailing Zeroes数论推导与 O(log n) 解法全解析LeetCode 172 阶乘后的零Factorial Trailing Zeroes数论推导与 O log n 解法全解析 本篇技术指南围绕 leetc文档教程知识库LeetCode-Go 精讲172. Factorial Trailing Zeroes 阶乘尾随零的数学推导与 O(log n) Go 实现LeetCode Go 精讲172. Factorial Trailing Zeroes 阶乘尾随零的数学推导与 O log n Go 实现 导读本文以 L示例工程上一篇免费开源的Nigate三步让Mac读写NTFS硬盘跨平台传文件不再求人下一篇EdgeRemover 实战教程1 分钟彻底卸载 Windows 10/11 的 Microsoft Edge创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
