1. 从一道小题说起为什么“数末尾0”值得单独写一篇“求N的阶乘末尾0的个数”——这题我第一次见是在一个算法练习列表里当时扫了一眼就觉得答案应该很简单算出来转成字符串数一下末尾有几个0不就完了结果真动手写的时候才发现N稍微大一点比如N100算出来的数就已经是个158位的庞然大物C语言里没有任何内置类型能直接装下。再往后N1000、N10000别说装了光是算出来这个数本身就要消耗大量时间和内存。所以这道题真正的考点从来不是“怎么数0”而是怎么在不真正算出这个巨大数字的前提下推导出它末尾0的个数。这背后涉及数论里一个非常经典的思想把问题从“计算结果”转化为“统计因子”。一旦想通这一层代码可以短到十几行而且N取多大都不怕。这篇小记就是把我自己从“暴力硬算”到“数学推导”再到“工程实现”的完整思路记录下来包括中间踩过的坑、参数怎么定、边界怎么处理。适合刚学C/C、正在刷算法题的朋友也适合想复习一下数论基础、顺便看看工程写法的人。核心关键词就三个阶乘、末尾0、因子5记住这三个词后面所有内容都围绕它们展开。2. 核心思路拆解末尾的0到底从哪来2.1 一个0就是一对2和5先从最朴素的观察开始。一个十进制整数末尾有几个0取决于它能被10整除几次。而10 2 × 5所以末尾0的个数本质上就是这个数里因子2和因子5配对的数量。举个例子10 2 × 5一对末尾1个0100 2² × 5²两对末尾2个0再比如25 × 4 10025里有两个54里有两个2配成两对末尾2个0。规律很清楚末尾0的个数 min(因子2的总数, 因子5的总数)。那为什么是min而不是别的因为配对必须成双2多了没用5多了也没用谁少谁说了算。就像做菜菜谱要求一勺盐配一勺糖你盐有10勺、糖只有3勺那最多只能做3份。2.2 阶乘里因子2永远比因子5多现在把场景换到N的阶乘。N! 1 × 2 × 3 × ... × N这里面每个数都可能贡献因子2和因子5。直觉上偶数比5的倍数多得多——每2个数就有一个偶数但每5个数才有一个5的倍数。所以因子2的数量必然远远超过因子5。这个直觉可以严格验证在1到N之间能被2整除的数有⌊N/2⌋个能被5整除的数只有⌊N/5⌋个而⌊N/2⌋ ≥ ⌊N/5⌋恒成立。再考虑2的幂次4、8、16…贡献更多因子25的幂次25、125…贡献更多因子5但即便如此因子2的总量依然碾压因子5。结论就出来了N!末尾0的个数 N!中因子5的总数。因为因子2管够瓶颈永远在5这边。这一步是整个解法的关键转折把“数2和5”简化成了“只数5”。2.3 为什么不能直接算阶乘有人可能会想那我用大数库比如自己写个高精度乘法把N!算出来再数末尾0不行吗行但没必要而且代价很大。算一下复杂度N!的位数大约是N·log10(N)级别。N10000时结果有35660位左右也就是约3.5万个十进制位。用高精度乘法逐个数相乘每次乘法都要遍历整个大数数组总运算量是O(N²)级别N10000时就是上亿次基本操作还得额外维护一个几万位的数组。而用因子5的数学方法运算量是O(log₅N)N10000时只需要算五六次除法。两者差距是数量级的。提示算法题里凡是看到“阶乘”“末尾0”“大数”这几个词凑在一起第一反应就该是找数学规律而不是上高精度。高精度是最后的手段不是首选。3. 因子5怎么数从暴力到公式的推导3.1 第一层数5的倍数最直接的想法遍历1到N每个数看看能被5整除几次累加起来。伪代码大概是这样int count 0; for (int i 1; i N; i) { int x i; while (x % 5 0) { count; x / 5; } }这个写法正确但复杂度是O(N log N)N10⁹的时候直接超时。而且它没有利用任何数学结构属于“能跑但不够聪明”的版本。我一开始就是这么写的提交之后发现N给到10⁸就卡住了才意识到需要优化。3.2 第二层只数5的倍数优化思路不需要遍历所有数只需要看5的倍数。因为只有5的倍数才贡献因子5。所以循环可以改成int count 0; for (int i 5; i N; i 5) { int x i; while (x % 5 0) { count; x / 5; } }复杂度降到O(N/5 · log N)好了一些但本质还是线性遍历N很大时依然不够。3.3 第三层分层统计一步到位真正优雅的做法是分层统计。把1到N中所有数贡献的因子5分成几层来数第一层能被5整除的数每个至少贡献1个5。个数是⌊N/5⌋。第二层能被25整除的数每个额外再贡献1个5因为255²在第一层已经算过1个了。个数是⌊N/25⌋。第三层能被125整除的数每个再额外贡献1个。个数是⌊N/125⌋。以此类推直到5的幂超过N。为什么这样分层不会重复也不会遗漏可以这样理解一个数如果含有k个因子5它会在第1层、第2层、…、第k层各被数到一次总共被数k次正好等于它的因子5个数。比如25含有2个5它在第一层被5整除被数一次在第二层被25整除又被数一次合计2次正确。125含有3个5会在三层里各被数一次合计3次正确。于是公式就是count ⌊N/5⌋ ⌊N/25⌋ ⌊N/125⌋ ...用循环写出来long long count 0; long long power 5; while (power N) { count N / power; if (power N / 5) break; // 防止power*5溢出 power * 5; }这个循环最多执行log₅N次。N10¹⁸时5的幂最多到5²⁶左右循环不到30次瞬间出结果。3.4 参数与类型选择这里有个容易忽略的细节N的取值范围决定了用什么类型。如果题目说N ≤ 10⁹用int存N没问题但count可能超过int范围吗算一下N10⁹时count ≈ N/5 N/25 ... ≈ N/4 2.5×10⁸int约21亿装得下。但如果N到10¹⁸count约2.5×10¹⁷必须用long long约9.2×10¹⁸。所以稳妥起见count一律用long longpower也用long long避免中间计算溢出。另外那个if (power N / 5) break;是防溢出的经典写法。直接写power * 5有可能在power接近long long上限时溢出变成负数导致死循环。用除法判断更安全。4. 完整实现与实测记录4.1 基础版本代码把上面的思路整理成一个完整函数#include stdio.h long long trailingZeros(long long n) { long long count 0; long long power 5; while (power n) { count n / power; if (power n / 5) break; power * 5; } return count; } int main() { long long n; while (scanf(%lld, n) 1) { printf(%lld\n, trailingZeros(n)); } return 0; }这段代码可以直接编译运行输入N输出末尾0的个数。我实测了几个值N末尾0个数验证方式10210! 3628800末尾2个025625!末尾6个0可查证10024100/5100/25 204 2410002492004081 249100002499200040080163 2499N10000时公式算出来是2000400801632499和暴力法验证的结果一致。而暴力法算10000!需要处理3万多位的数耗时明显公式法瞬间完成。4.2 边界情况处理几个必须考虑的边界N00! 1末尾0个0。公式里power5 0循环不执行返回0正确。N5比如N44!24末尾0个0。公式返回0正确。N为负数阶乘对负数无定义实际题目不会给但工程上可以加个判断返回-1或0。N极大比如N10¹⁸用long long输入公式循环约27次结果约2.5×10¹⁷long long装得下。注意如果题目给的N超过long long范围比如用字符串输入的超大数那就需要另写大数除法但这种情况极少见一般算法题N都在10¹⁸以内。4.3 暴力验证脚本为了确认公式没错我写了个暴力版本做对拍#include stdio.h // 暴力法直接数每个数的因子5 long long bruteForce(long long n) { long long count 0; for (long long i 5; i n; i 5) { long long x i; while (x % 5 0) { count; x / 5; } } return count; }把两个函数对N从1到10000跑一遍结果完全一致。这种对拍是验证数学推导最可靠的方式比单纯看公式推导更让人放心。5. 常见问题与排查技巧实录5.1 为什么我算出来结果偏小最常见的原因是只算了⌊N/5⌋忘了加上25、125这些高次幂的贡献。比如N25只算25/55但正确答案是6因为25本身贡献了2个5少算了1个。排查方法拿N25、N125这种5的幂去测如果结果和预期差1或差2基本就是这个原因。5.2 溢出导致的错误结果如果N很大而count用了int可能溢出成负数。比如N10⁹时count约2.5×10⁸int还装得下但N10¹⁰时count约2.5×10⁹超过int上限约2.147×10⁹就会溢出。排查方法把count类型改成long long重新测。另一个溢出点是power * 5。如果power已经接近long long上限乘5会溢出。用if (power n / 5) break;提前终止或者用while (power n / 5)作为循环条件。5.3 循环条件写错导致死循环有人写while (power n) { count n/power; power * 5; }当power溢出成负数时power n依然成立负数小于正数循环永远不结束。这是典型的溢出死循环。解决办法就是加溢出判断或者用除法形式写循环条件。5.4 常见问题速查表现象可能原因解决方法结果比预期小漏算高次幂检查是否累加了N/25、N/125结果为负数count类型溢出改用long long程序卡死power溢出导致死循环加power n/5判断N0时结果不对循环条件没处理好确认power5 0循环不执行大N超时用了暴力遍历改用分层统计公式5.5 一个容易忽略的细节有些题目会问“N!的末尾有多少个0”但N可能是用字符串给的大数。这种情况下如果N的位数不超过18位可以用strtoll转成long long再算如果超过18位就需要手写大数除以5的运算。不过这种题很少见大部分在线判题系统的N都在long long范围内。6. 从这道题延伸出去的思考这道题表面上是数0实际上训练的是把具体问题抽象成数学结构的能力。类似的思路在很多地方都能用求N!中因子2的个数公式完全一样把5换成2即可。求N!中某个质因子p的个数公式是⌊N/p⌋ ⌊N/p²⌋ ...这是勒让德公式的特例。判断组合数C(N, M)的奇偶性可以用因子2的个数来判断。求N!末尾在K进制下的0的个数需要分解K的质因子取各因子配对数的最小值。这些延伸问题的核心都是同一个不直接算大数而是统计质因子的贡献。掌握了这个思想一类问题就都能解决了。我个人在实际写代码时的体会是遇到“阶乘大数末尾”这种组合先别急着动手写循环花两分钟想想数学规律往往能把O(N)甚至O(N²)的问题降到O(log N)。这个思考习惯比记住某一道题的答案更有价值。
