很多年以前刷OJ的时候碰到过一道题号1066的阶乘题题名是Last non-zero Digit in N!。题目问得很简单给一个非负整数N输出N!从右往左数第一个不是 0 的数字。但难点在于——这个N不是通常的 32 位整数而是可以大到上千位的超大数。题目的核心标签是大数、模除也就是不能直接算N!而是要在去掉所有末尾 0 的过程中用数论办法把问题缩小。这篇文章就把完整推导、字符串除法的实现、以及各种边角坑都讲清楚。如果你正在刷阶乘类题目或者曾经用高精度硬算N!超时那么这篇文章应该能帮你省下不少时间。我尽量把每一步“为什么这么做”也写出来而不是只丢一个 AC 代码。1. 为什么“N!”不能硬算问题规模、溢出和末尾零的真相1.1 题目到底要我们输出什么先看几个小数据建立感觉NN!最后一个非零数字011111222366424451202672027504048403202936288081036288008注意5! 120左边是120去掉末尾 0 后是12最后一位就是 2。10! 3628800去掉两个 0 后是36288最后一位是 8。也就是说题目跟“这个数有多大”没关系只关心去掉所有因子 10 之后剩下的个位数字。1.2 高精度模拟为什么不可行一个常见思路是既然N很大那我用高精度数组或者 Python 的大整数直接把N!算出来再逐位找非零数字。这个思路在N很小时没问题但到了几千位的大数就会彻底失败。原因可以从两个层面看。第一是数值规模N!的十进制位数大约等于N * log10(N)当N是一万时就已经有四万多位当N是一千位左右的超大整数时N!的位数根本无法想象连存储都成问题。第二是乘法复杂度就算咬着牙用高精度乘法硬乘N!的二进制长度也在不停膨胀整体复杂度会达到接近O(N² log N)甚至更糟输入稍微大一点就超时。所以这道题实际上在提醒我们遇到阶乘问题不要总想着把阶乘“算出来”。我们应该思考N!末尾的 0 是怎么来的以及去掉这些 0 之后剩下的数字能不能通过某种周期性规律直接递推出来。1.3 末尾零来自因子2和因子5的配对十进制里一个数末尾有一个 0就代表它被 10 整除了一次而10 2 × 5。所以N!末尾 0 的数量等于 1 到N中因子 2 和因子 5 能配成的对数也就是末尾0个数 min(c2, c5)其中c2是N!中因子 2 的总个数c5是因子 5 的总个数。在阶乘里2 的倍数比 5 的倍数多得多所以永远是c2 c5末尾 0 的个数实际上就等于c5。如果我们想得到“去掉末尾 0 后的最后一位数字”本质上是把N!先除掉10^c5也就是答案 N! / (2^c5 × 5^c5) mod 10换句话说要从N!中把因子 2 拿走c5个把因子 5 也拿走c5个剩下的乘积的个位就是答案。到这一步问题已经从一个“巨大整数的阶乘”变成了“跟踪因子 2 和因子 5 的数量”。后面要做的就是把这一句话转化为可迭代的递推公式。2. 数学递推把因子5拿掉后周期自然出现2.1 定义h(N)刨掉所有因子5的N!为了处理因子 5先定义一个辅助函数h(N)h(N) N! 中所有因子5都被去掉后剩余部分的乘积更准确地说对 1 到N的每个数把其中包含的因子 5 全部提出来拿掉例如 25 要除掉两个 5125 要除掉三个 5然后把剩下的数全部乘起来。h(N)不再含因子 5但它仍然保留着所有因子 2。这个函数可以递归计算。把 1 到N分成两类不是 5 的倍数的数和是 5 的倍数的数。是 5 的倍数的数写成5, 10, 15, ..., 5*⌊N/5⌋每个数先贡献一个因子 5剩下的部分正好是1, 2, 3, ..., ⌊N/5⌋。所以N! A(N) × 5^⌊N/5⌋ × ⌊N/5⌋!其中A(N)是 1 到 N 中所有不是 5 的倍数的数的乘积。把这个式子两边都去掉所有因子 5就得到核心递推h(N) A(N) × h(⌊N/5⌋)这个递推非常漂亮h(N)只依赖于A(N)和更小的h(⌊N/5⌋)。换句话说每迭代一次问题的规模就除以 5。2.2 A(N)的周期结构每5个数一组乘积模5是-1现在要处理A(N)。它不是 5 的倍数的那些数的乘积模 5 有很强的周期性。看每 5 个连续整数5k1, 5k2, 5k3, 5k4它们都不是 5 的倍数乘积模 5 等于1 × 2 × 3 × 4 ≡ 24 ≡ 4 ≡ -1 (mod 5)也就是说每完整的一组 5 个数非 5 倍数部分的乘积模 5 就是 -1。那么对于N 5q r其中0 ≤ r 5可以得到A(N) ≡ (-1)^q × r! (mod 5)这里的r!不是真实的阶乘而是模 5 下的结果。因为尾部的5q1, 5q2, ..., 5qr模 5 分别是1, 2, ..., r它们相乘就是r! mod 5。这个结论让h(N)的递推变得很具体。假设当前处理到某个n令q ⌊n/5⌋r n mod 5那么h(n) A(n) × h(q)A(n) ≡ (-1)^q × r! (mod 5)所以每轮迭代只需要取n的个位作为r查一个小表得到r! mod 5再把n除以 5 得到q如果q是奇数就额外乘一个 -1。2.3 因子2的补偿为什么还要除2^{v5(N)}有了h(N)还不够因为最终答案要求把因子 2 也拿走c5个。h(N)保留了所有因子 2所以答案对应的数 h(N) / 2^{c5}这里c5就是 5 的因子总个数通常记为v5(N)v5(N) ⌊N/5⌋ ⌊N/5²⌋ ⌊N/5³⌋ ...问题来了我们想知道h(N) / 2^{v5(N)}的个位。直接对模 10 做除法很麻烦因为 2 在模 10 下没有逆元。一个更聪明的办法是转到模 5 下计算。在模 5 下2 的逆元存在2 × 3 ≡ 6 ≡ 1 (mod 5)。所以答案 mod 5 ≡ h(N) × 3^{v5(N)} mod 5也就是说最终只需要知道两样东西h(N) mod 5用刚才的递推解决v5(N) mod 4因为 3 的幂模 5 的周期是 4。3^0 1, 3^1 3, 3^2 9 ≡ 4, 3^3 27 ≡ 2, 3^4 81 ≡ 1周期确实是 4。2.4 从模5结果恢复真实个位最后要把模 5 的结果映射回真实的个位数字。这里有个关键观察当 N≥2 时去掉末尾 0 后的结果一定是偶数因为N!中 2 的因子数比 5 的因子数多除掉配对的因子 2 后至少还剩下一个 2所以最后一位只能是 2、4、6、8 之一不可能是 0因为末尾 0 已经全部去掉了。那么已知答案x满足x mod 5 t且x是偶数就能唯一确定t x mod 5真实个位 x16223844为什么t1对应 6 而不是 1因为 1 不是偶数。同理t3对应 8 而不是 3。这样就能安全地从模 5 恢复出真实个位。3. 大数除以5整个算法真正的“大数”难点3.1 不需要高精度乘法只要十进制长除法现在剩下的工程问题只有一个N可能是上千位的大数我们怎么求⌊N/5⌋和N mod 5很多人看到“大数”就以为要写高精度乘法、高精度数组其实这道题完全不用。因为每一步只需要把当前数除以 5然后把商继续作为下一个数处理。这就是反复做十进制长除法。为什么要除以 5因为递推公式h(N)里的核心操作是N - ⌊N/5⌋而且最后还要统计v5(N)这也是反复除 5 求和。整个算法本质上就是把大数N不断缩小直到变成 0期间记录余数和商的大小。3.2 字符串长除法div5的实现细节手算12345 ÷ 5的过程是这样的从最高位 1 开始1 不够除 5商 0余数 1把下一位 2 拉下来变成 1212 ÷ 5 2 余 2把下一位 3 拉下来变成 2323 ÷ 5 4 余 3把下一位 4 拉下来变成 3434 ÷ 5 6 余 4把下一位 5 拉下来变成 4545 ÷ 5 9 余 0。所以12345 5 × 2469商是2469余数是 0。写成字符串处理用一个变量carry记录上一步的余数每轮合并当前数字// 把字符串 n 除以 5得到商 q 和余数 r void div5(const string n, string q, int r) { q.clear(); int carry 0; for (char ch : n) { int cur carry * 10 (ch - 0); int digit cur / 5; carry cur % 5; if (!q.empty() || digit ! 0) { q.push_back(char(0 digit)); } } if (q.empty()) q 0; r carry; }这段代码要特别注意两个细节。第一商的前导 0 要扔掉比如12345第一步商0不应该出现在结果里只有当后续出现非零数字时才允许加入第二如果整个数小于 5商应该为0余数就是原数的个位例如4除以 5商0余数4。3.3 商串的奇偶和模4只看末几位在递推过程中我们还需要频繁知道两件事商q是奇数还是偶数以及q mod 4是多少。因为(-1)^q mod 5当q为奇数时等于 -1也就是 4当q为偶数时等于 1v5(N) mod 4需要把每一轮商q的模 4 值累加。一个十进制整数判断奇偶只需要看最后一位数字。判断mod 4只需要看最后两位数字因为100是 4 的倍数10^k (k≥2)都被 4 整除。所以可以不用把q转成真正的整数直接对商字符串操作bool isOdd(const string s) { return (s.back() - 0) % 2 1; } int mod4(const string s) { if (s.size() 1) return (s[0] - 0) % 4; int lastTwo (s[s.size() - 2] - 0) * 10 (s[s.size() - 1] - 0); return lastTwo % 4; }这两个函数非常轻量避免了每次把大数转换成整数可能出现的溢出风险。3.4 循环次数与总复杂度每除以 5 一次大数的数值大约缩小到原来的五分之一。一个十进制数每减少一位大约需要除以多少次 5因为10^{k} ≈ 5^{k × log5(10)}更直观点log10(5) ≈ 0.699所以每除一次 5十进制位数平均减少约 0.7 位。假设输入的N有L位那么循环次数大约是L / 0.699 ≈ 1.43L次。例如 1000 位的超大数大约需要循环 1430 次。每次长除法要遍历当前数字的每一位而每一轮数字都在变短整体复杂度为O(L²)级别。L1000时操作量不到两百万次跑起来非常轻松。4. C实现与样例验证4.1 完整AC风格代码下面这个版本可以直接提交。代码里我对前导 0 做了处理避免输入000这类数据造成边界错误。#include iostream #include string using namespace std; // n / 5商写入 q余数写入 r void div5(const string n, string q, int r) { q.clear(); int carry 0; for (char ch : n) { int cur carry * 10 (ch - 0); int digit cur / 5; carry cur % 5; if (!q.empty() || digit ! 0) { q.push_back(char(0 digit)); } } if (q.empty()) q 0; r carry; } bool isOdd(const string s) { return (s.back() - 0) % 2 1; } int mod4(const string s) { if (s.size() 1) return (s[0] - 0) % 4; int lastTwo (s[s.size() - 2] - 0) * 10 (s[s.size() - 1] - 0); return lastTwo % 4; } string trimLeadingZeros(string s) { size_t pos s.find_first_not_of(0); if (pos string::npos) return 0; return s.substr(pos); } int solve(const string input) { string n trimLeadingZeros(input); if (n 0 || n 1) return 1; // 0! 和 1! 的特殊情况 int factMod5[5] {1, 1, 2, 1, 4}; // 0!,1!,2!,3!,4! 模5 int h 1; // h(n) 模5 int v5mod4 0; // v5(N) 模4 string cur n; while (cur ! 0) { string q; int r; div5(cur, q, r); h (h * factMod5[r]) % 5; // 乘上 r! v5mod4 (v5mod4 mod4(q)) % 4; if (q ! 0 isOdd(q)) { h (h * 4) % 5; // 乘上 -1 mod 5 } cur q; } // 乘上 3^{v5(N)} mod 5 int threePow[4] {1, 3, 4, 2}; // 3^0, 3^1, 3^2, 3^3 h (h * threePow[v5mod4]) % 5; // 映射回真实个位 int mapAns[5] {-1, 6, 2, 8, 4}; return mapAns[h]; } int main() { string s; while (cin s) { cout solve(s) \n; } return 0; }4.2 核心代码逐行注释代码里最容易看晕的是h的维护过程。我再把整个思路用中文串一遍。h一开始是 1代表空乘积。每一轮我们从当前cur取出商q和余数r。根据递推公式h(cur) A(cur) × h(q)而A(cur) mod5 (-1)^q × r! mod5。所以这一轮要把h乘上r!然后在下一轮的时候如果q是奇数就再补一个 -1。代码里的顺序是先乘factMod5[r]然后立刻判断当前q是否奇数是就乘 4。这样写本质上跟在“下一轮开头乘 -1”是一样的因为模 5 乘法满足交换律。v5mod4累加的是每一轮q的模 4。注意v5(N)的定义是v5(N) ⌊N/5⌋ ⌊N/5²⌋ ⌊N/5³⌋ ...第一次循环拿到的q ⌊N/5⌋第二次循环拿到的q ⌊N/5²⌋以此类推每次循环的q正好就是级数里的一项。所以把每一轮的q mod 4累加起来就得到了v5(N) mod 4。最后threePow数组就是3^k mod5的查询表直接用v5mod4查表比写循环快也更直观。4.3 手工验证一组数据我用N 100演示一下整个状态变化方便你在脑子里跑一遍代码。轮次curqrfactMod5[r]h更新v5mod4q奇偶补偿110020011×110q20为偶数不乘2204011×110q4为偶数不乘340441×440q0结束所以h(100) ≡ 4 mod5v5(100) mod4 0最后h × 3^0 ≡ 4 mod5查映射表4 → 4答案是 4。而100!去掉所有末尾 0 后的最后一位确实是 4。再看N 25轮次curqrfactMod5[r]h更新v5mod4q奇偶补偿12550111q5为奇数h→42510142q1为奇数h→13101112结束h ≡ 1v5mod4 2乘3² ≡ 4得到4 mod5映射还是 4。25!的最后一个非零数字确实是 4。4.4 边界情况0、1、前导0、超大N代码开头对n 0 || n 1做了特判输出 1。这一步不能省因为模 5 算法在N1时会算出h1, v50最终ans mod5 1如果机械地映射会得到 6 而不是真实的 1。原因就是前面说的“答案一定是偶数”只对N≥2成立0!和1!是例外。前导零也必须处理。比如输入0005如果不做trimLeadingZeros第一次div5会把商算成1过程虽然歪打正着能过但如果输入是00000它会被当成非 0 字符串进入循环最后得到 6 而不是 1。所以稳妥的代码一定要先把字符串转成规范形式。对于超大N这个代码没有任何额外压力因为全程没有把大数转成整数也没有高精度乘法。它只是在字符串上反复做除以 5 的运算属于“看着像大数实际上只是模拟小学除法”。5. 容易掉进去的坑与替代方案5.1 三种常见的错误做法第一个错误是直接对 N 取模或者硬算。有人看到“最后一个非零数字”就试图算N!哪怕N只有几十用long long也存不下。更关键的是即使存得下简单取模也忽略了末尾 0 的清除过程答案没有任何规律可言。比如15!的最后非零数字是 8但15 mod 10 5两者没有直接关系。第二个错误是固定周期打表。网上确实能看到一些按“每 10 个一组”找周期的写法这些写法本质上也在处理因子 2 和 5但很容易忽略N很大时“组数”本身还带着因子 5需要递归处理。如果只是把1..10的乘积去掉 0 后当成一个魔数循环乘那么遇到N25这类组数本身还含 5 的情况就会算错。第三个错误是试图在模 10 下除以 2。数学上2在模 10 下没有逆元所以不能直接乘1/2。这也是我选择先转模 5 的原因。模 5 是一个质数模数2 有逆元 3一切都能干净地计算。5.2 “模除”到底是什么这道题标签里的“模除”很容易让人误解以为是用大数取模。其实真正的核心操作是反复把大数除以 5 并取余数。大数取模求的是N mod 5这只是一次除法而这道题需要的是不断执行N floor(N/5)每次还把商的奇偶、模 4 都收集起来。所以它是“模”和“除”的结合每一步都在做除法同时每一步都在用余数做模运算。如果把“模除”换成大白话就是一手用长除法把大数不断缩小另一手把商的信息通过模运算提取出来。理解了这一点题目的代码其实非常短。5.3 扩展一求最后两位非零数字如果题目从“最后一位非零数字”变成“最后两位非零数字”整体思路仍然成立。最后两位需要模 100而模 100 不能直接处理因子 2应该把问题拆成模 4 和模 25 两部分最后用中国剩余定理合并。因子 5 的递归结构依然存在但A(N)的周期会变长不再只是每 5 个数一组而是需要观察模 25 下的周期。复杂度会上升但思想完全一致。5.4 扩展二换成任意质数p如果把题目里的 5 换成任意质数p同样可以做。思路是先统计N!中因子p的个数再把所有数中因子p全部拿掉剩下的部分模p-1或者模p找周期。因为p是质数模p下非p倍数的数构成乘法群所以A(N)的周期可以借助费马小定理找到。这个题目其实就是一类“阶乘尾部零与周期”问题的入门代表学会之后可以迁移到很多变式。最后分享一个实际调试的小体会我在写这个题的过程中最容易被绕晕的地方不是递推公式而是“每轮该乘 -1 还是下一轮乘”。后来我换了一个方式记忆先别看代码只记一句话——每一个完整五块都让 h 变一次号。也就是说只要当前得到的商不是 0而且商是奇数就说明前面有几个不完整的五块被漏掉了h 要翻一次正负。这样想之后调试起来就顺多了。另外如果你自己写测试数据建议把0、1、5、25、125这几个都跑一遍它们最容易暴露边界问题。当初我用125测试时发现映射表少写了一个值这类细节只有亲手跑数据才会注意到。
