开学第一周ACM社团的新生群里就炸开了锅好几个大一小朋友都在刷同一道题ZZULIOJ 2871题目名很唬人叫“小T的魔法数字”标签是“阶乘算法大一水平”。说实话光看这个标签你就能猜到出题人想干什么——不是让你真的把阶乘算出来而是看你懂不懂阶乘背后的数学规律。很多新生一上来就long long sum 1; for(i1; in; i) sum * i;然后发现要么溢出要么答案跟样例对不上最后卡在WA里怀疑人生。这道题我拉出来给新生讲了好几遍每次都要先强调一句话OJ考阶乘从来都不是考你算阶乘而是考你敢不敢不算阶乘。下面我把这道题的完整拆解、代码模板、以及新生最容易踩的坑一次性讲清楚看完你不仅能AC这一题以后再碰到阶乘类的变体题也能有个大致方向。1. 题面解读它到底想考你什么1.1 为什么不能直接算n!先换个角度看问题。如果你拿到的是“小T的魔法数字”题面大概率是给定一个正整数 n让你求 n! 的某个特殊性质。按最常见的出题套路这个特殊性质就是n! 末尾连续 0 的个数也有可能是 n! 除以某个数之后的余数、n! 中有多少个因子 x或者判断 n! 能否被某个 m 整除。先说为什么不能直接算 n!。以 n20 为例20! 等于 2432902008176640000这个数字已经超过了 int 的范围甚至逼近 long long64位有符号整数的上限。换句话说n 只要到 21再往后乘 long long 也要爆。所以在大一阶段的任何阶乘题里只要你看到 n 的范围给到 10^9 甚至更大就能立刻判断题目绝对不是让你线性乘过去它想要的是一个不需要把完整阶乘构造出来的数学解法。这里还要给一些刚入OJ的同学提个醒C语言的 int 通常只有4字节能表示的最大值是 2147483647long long 是8字节最大是 9223372036854775807。超过这个范围叫“有符号整数溢出”在C语言里是未定义行为OJ上最常见的表现不是报错而是算出个莫名其妙的负数或错误答案。所以面对阶乘题第一反应应该是“这个数会不会爆”而不是急着开循环。1.2 “魔法数字”最常见出题版本因为这里没有给出具体的样例输入输出我基于OJ上这类题目的普遍设计把最容易出现的三个版本列出来你看完就明白为什么核心思路是通用的版本A求 n! 末尾连续0的个数。比如 n1010! 3628800末尾有2个0输出2。这是最经典的入门数论题也是“小T的魔法数字”最可能的原型。版本B求 n! 中因子 k 的个数。本质就是在问 n! 的质因数分解里某个素数的指数是多少这个和版本A是同一个解法。版本C求 n! 对 m 取模。如果 m 很小也有办法用滚动取模去做但这个不属于“魔法数字”题的核心套路通常出题人不会拿来为难大一新生。我个人比较推荐你按版本A来理解这道题因为它的数学原理最漂亮代码最短而且和大一上学期学过的整数分解、整除性质完全挂钩。题面里“魔法数字”四个字说白了就是忽悠你往“神奇规律”上想而那个规律就是下面要讲的因子5计数法。2. 核心原理末尾零为什么等于数因子52.1 把“末尾0”翻译成数学语言这个点理解透了整道题就通了。一个十进制整数末尾每有一个0就说明它能被10整除一次。而 10 2 × 5。所以一个数末尾连续0的个数就等于它质因数分解里“2×5”配对的个数也就是 min(因子2的个数, 因子5的个数)。我上课时喜欢用“木桶效应”来讲末尾0的数量取决于短板2和5哪个少哪个就决定最终能拼出多少个10。现在把 n! 看成从 1 乘到 n每个数都分解成质因数那么因子2的个数和因子5的个数分别是多少直观感受一下从1到n偶数占一半每隔一个数就有一个2而5呢每5个数才出现一次。显然因子2的个数远远多于因子5的个数。所以末位0的个数直接等于因子5的个数。这个“短板”一定在5这一侧。2.2 为什么是 n/5 n/25 n/125 ...现在问题变成了求 n! 的质因数分解里到底有几个因子5。一个个数肯定不行n 最大可能到10^9级别。但是我们可以换一个计数方式先数 1 到 n 中有多少个数是 5 的倍数个数是 ⌊n/5⌋再数有多少个数是 25 的倍数个数是 ⌊n/25⌋再数 125 的倍数个数是 ⌊n/125⌋……一直加下去直到除数大于 n 为止。为什么这样加不会重复因为一个数是 25 的倍数它本身已经提供了两个因子5但它在“5的倍数”那一层只被算了一次所以第二层再加一次就正好补上第二个因子5。同理125的倍数提供了三个因子5前两层已经算了两次第三层再加一次就齐了。每一层都在补齐“该数额外多出来的因子5”所以累加结果就是 n! 中因子5的总个数。举个具体的例子n25第一层25 ÷ 5 5表示1到25里有5个数5,10,15,20,25能被5整除提供5个因子5第二层25 ÷ 25 1表示25本身还能再多贡献1个因子5总数是516。验证一下25! 末尾确实有6个0。你要是怀疑可以自己用计算器乘一下25!或者用Python的math.factorial(25)验证结果是15511210043330985984000000末尾正好6个0。2.3 终止条件与整型边界这个循环怎么停你可能会想写 while(n) { cnt n/5; n / 5; }这是标准写法因为每次 n 除以5后下一层除数相当于自动扩大5倍。注意这里 n 是不断缩小的比如 n 初始是 100第一次加 20n 变成 20第二次加 4n 变成 4第三次 4/5 得 0循环结束。加出来的总数是 20424也就是 100! 末尾有24个0。这里有一个大一同学特别容易忽略的坑第一层循环里 n 是原n越往后 n 越小千万不要用 for(i5; in; i5) 这种写法因为 i5 在 n 很大的时候会溢出。** 比如 i 从5一直乘到5的14次方早就超过int上限了。哪怕你声明 long long i在极端数据下同样会有问题。相比之下直接让 n 不断除以5整个过程没有任何乘法溢出的风险。3. 代码实现5分钟写出满分答案3.1 完整C语言代码按ZZULIOJ的评测习惯大一阶段用的基本都是C语言这里给出C语言版本的示例代码#include stdio.h int main() { int n; while (scanf(%d, n) ! EOF) { int cnt 0; while (n) { cnt n / 5; n / 5; } printf(%d\n, cnt); } return 0; }如果题目只有一个测试用例去掉 while(scanf(...) ! EOF) 的外层循环直接读 n 输出即可。但OJ上很多题都是多组测试数据所以我在模板里保留了这个外层结构这也是ZZULIOJ这类平台的常见输入方式。3.2 逐行解读这段代码很多同学能背下来这个代码但问他为什么 n 要不断除以5他就说不清了。这里我给你拆开讲清楚。首先本题的核心是“计数因子5的个数”所以循环变量用一个整型 cnt 来累加。每进入一层循环当前 n 表示的是“还有多少个数字能被当前这一层的除数整除”。第一轮 n/5 统计5的倍数个数第二轮 n/25 等价于 (n/5)/5也就是先让 n 变成 n/5再除以5得到 n/25。这就是代码里 n / 5 的含义。整个循环的时间复杂度是 O(log₅ n)。什么意思呢当 n10^9 时循环大概执行13次几乎可以忽略不计。这就是算法题里常说的“数学解法替代暴力解法”的典型代表——暴力做要乘10^9次数学做只需要13次。3.3 如果题面要求多组输入怎么改都通用ZZULIOJ 的很多题目不会明说“多组测试”但样例输出往往是多行的。一个比较稳的习惯是见到所有输入型题目先用 EOF 风格的循环去读本地造数据测一测再确认是否单组。如果你只写了单组输入版本而题目实际给多组大概率你会得到一个 Output Limit Exceeded 或者 WA因为程序只处理了第一组就退出了。针对这个模板我再说一个细节EOF 宏定义在 stdio.h 里值是 -1。scanf 读到文件尾时会返回 EOF所以 while(scanf(%d, n) ! EOF) 的意思就是“一直读到没有输入为止”。这个写法在大一阶段出现频率极高建议直接背下来能省很多不必要的调试时间。4. 大一新手最容易踩的五个坑4.1 多重测试时忘记重置计数器这是我改作业时见过最多的错误。有些人把 cnt 定义在 while 循环外面但每次处理完一组数据后没重置 cnt导致第二组数据的结果把第一组的结果加进去了。比如第一组输出2第二组真实答案也是2但程序输出了4。排查方法很简单把 int cnt 0; 写在 while 循环体内。这样每一组数据进入循环时自动从0开始逻辑上不会串。4.2 把 n 改掉了后续没法继续用有些同学想先存一份原始输入但代码里顺手就把 n 在循环里除没了。如果后面还需要原 n 做其他判断你就得再用一个变量保存原始值。比如int temp n; while (temp) { cnt temp / 5; temp / 5; }这样 n 本身不受影响。虽然本题只要输出结果用不到原 n但这个习惯建议养成——真实比赛里一个数经常要参与多次运算一上来就被“销毁”了会很麻烦。4.3 把 int 换成 long long 的时机要看题面数据范围。如果 n 最大不超过 10^9int 足够。但如果 n 给到 10^18int 直接溢出连 scanf(%d) 都会出问题必须用 long long。我建议你在读题时顺手看一眼数据范围如果题面没给就用更大的 long long 去读最多浪费几个字节但能避免很多隐患。另外注意输出格式long long 对应的格式控制符是 %lld不是 %d。这个写错在OJ上会WA而且在本地编译器上往往看不出问题因为内存布局的偶然性可能让你“碰巧”得到正确结果。4.4 本地跑得好好的提交就WA最常见的元凶有两个一个是多组输入处理方式不对另一个是函数命名冲突。比如你把变量命名为 time、index、left这些在C语言里都是标准库函数或关键字虽然有时候能编译通过但在特定环境下会引发奇怪的问题。我曾经见过一个新生把变量叫 delete结果在C编译环境下直接报错C语言环境下却没事。建议变量名尽量用 cnt、sum、ans、temp、n、m 这种能看懂且不碰关键字的词。这既是好习惯也是减少踩坑成本的手段。4.5 不知道在线OJ怎么评测无法本地复现刚接触OJ的同学经常遇到一个困惑代码在自己电脑上跑样例是对的但提交到ZZULIOJ上就是“答案错误”。可能有几个原因编译器不同。本地用的是较新版本GCCOJ可能用的是旧版本对某些语法比如 C99 特性支持程度不同。稳妥做法是不要用 for(int i0;...) 这种C99写法如果你用的OJ默认是C90就必须把变量声明放在代码块最前面。中文输入或输出。哪怕你只在注释里写了中文某些OJ的旧评测机也可能因为编码问题出意外。建议代码里一律用英文注释或者干脆不写注释。数组越界。有些题需要开数组你开了大小为 n 的数组但访问了 a[n]这在本地可能不崩在OJ上却会造成运行时错误。这类问题通常伴随 Runtime Error 的提示。5. 举一反三从这道题到组合数与大数据5.1 如果是求 n! 对 m 取模该怎么做聊完了末尾0说说同类的变体。有时候题面会改成“求 n! 对 1000000007 取模的值”。这种就不能用因子计数了得用另一个技巧边乘边取模。long long ans 1; for (int i 1; i n; i) { ans ans * i % mod; } printf(%lld\n, ans);原理是模运算的乘法性质 (a × b) % mod ((a % mod) × (b % mod)) % mod。所以每一步都取模就能把中间结果控制在 mod 以内避免溢出。注意这里 n 不能太大如果 n 有10^9级别这个 O(n) 的循环还是太慢得往阶乘的数学公式方向想但那已经超出大一水平的范围了。5.2 组合数末尾零C(n, m) 里有多少个0如果你对“数因子”的思路已经吃透了那可以进一步看看组合数的末尾0怎么求。组合数 C(n, m) n! / (m! × (n-m)!)末尾0的个数等于分子因子5的个数减去分母因子5的个数。用刚才的函数分别算三个阶乘的因子5个数一减就出来了。这个知识点在很多OJ题里都会被考到尤其是数学类题目。看起来是个新题其实底层还是同一套“因子计数法”。这也是为什么我反复强调理解算法的数学本质比背代码重要得多。5.3 因子计数能否扩展到其他素数完全可以。刚才我们数的是因子5如果题目问“n! 中有多少个因子2”那就写 n/2 n/4 n/8 ...。换成任意素数 p同一套循环改成除以 p 就行。如果是判断“n! 能否被 m 整除”本质上就是看 m 的每个质因子在 n! 里的个数是否都不少于 m 里对应质因子的个数。这种题看起来复杂分解完质因数后还是用“除法累加”的老方法来计数。你会发现大学新生算法题里很多高难面孔的背后都是几个基础数学工具的组合。把“除法计数”这一招练熟就能应对一大片阶乘相关的问题。5.4 数据范围变大时还需要注意什么如果 n 到了 10^18 级别C语言的 long long 也快撑不住了但好在本算法里只有加法和除法结果最多是 n 的数量级不会爆。不过读入要用 %lld。如果数据范围到 10^100 这种天文数字那就得上大数处理了ACM里通常用字符串读入再模拟大数除法。但作为大一题目几乎不可能出现这种情况你只需要知道有这种扩展即可不用过早焦虑。6. 说说我帮新生调这道题的几个真实案例6.1 案例一样例能过但交上去就是WA一个新生跑来找我代码思路完全正确本地测 5、10、25 都能对上但提交就是WA。我让他把代码发过来一眼看到问题int n; while (scanf(%d, n)) { ... }这个写法的问题在于scanf 返回的是成功读取的参数个数正常读到数字时返回1循环继续可一旦读到文件尾返回的是 EOF即-1而 -1 在条件判断里是“真”循环还会继续进入导致 n 的值是上一次残留下的旧值又算了一遍然后这个错误的输出还会再打印一次。多组输入的最后就会多出一行错误答案。正确写法是 while(scanf(%d,n) ! EOF) 或者 while(scanf(%d,n) 1)。这个坑非常经典我至少见过十几次。6.2 案例二题目最大值是 int却非要用 int 导致乘法溢出还有个同学写的是这个版本int result 1; for (int i 1; i n; i) { result * i; } while (result % 10 0) { count; result / 10; }他以为边乘边去掉末尾的0就不会溢出想法不错但没仔细想result 即使去掉了0仍然可能是一个巨大的数。比如 20! 去掉末尾4个0后剩下的数字仍然有十几位。只要中间任何一次乘法结果超过 int 上限整个循环就乱了后面的取模和除以10都会在错误的基础上进行。这个问题说明他没有真正理解“为什么不能用乘法”的本质只是简单地想了个折中方案。后来我用上一节讲的因子5计数法帮他写了一遍他才知道原来只需要几行循环就够了根本不需要碰乘法。他感慨说“早知道数学这么有用高中就好好学数论了”。6.3 案例三循环变量用错了类型有人写 for(int i5; in; i*5)当 n 很大时 i 溢出变成负数循环条件永远成立死循环本地跑直接卡死交到OJ上就TLE超出时间限制。这个问题我在前面已经点过一次这里再强调一下凡是循环变量要不断乘以某个数的题都要警惕乘法溢出。最稳的写法就是反过来除也就是让 n 每次都除以5而不是让 i 每次都乘以5。7. 一点心得体会这道题在ZZULIOJ里的难度并不高但它是个很好的“分水岭”大一新生里能自己想到用“因子5计数法”而不是硬算阶乘的人说明已经开始建立“算法的本质是用更聪明的方式解决问题”这一意识。而只会硬算的人可能在遇到任何题目时都会本能地先把循环写出来再说这种思路不能说错但天花板很低。我个人的体会是刷OJ不能只看自己AC了几道题更要看每道题让你“改掉了什么习惯”。如果你的代码能从“能跑”变成“算得快、空间省、想得透”那这一道题花再多时间都值。希望这篇拆解能帮你在“小T的魔法数字”上打开思路顺便把阶乘这一类题彻底拿下。