HDU1066题解：大数阶乘去零末位与字符串模除实现

“HDU1066”这道题我印象很深标题很直白给一个超大整数 N求 N! 去掉末尾全部 0 之后剩下数字的个位是多少。题目短坑不少难度也集中在两点一个是很多人会直接对 10 取模结果白交几发另一个是 N 的位数可能上百位普通整数类型根本装不下。这道题很适合拿来练手因为把“阶乘尾零”这个经典模型、大数取模、字符串除法、打表找周期这些常见的竞赛技能全串起来了。如果你准备算法竞赛或者想搞懂“大数情况下怎么求阶乘末位非零数字”这篇应该能帮上忙。1. 先看清题目在问什么别急着让阶乘裸奔很多新手看到“最后一位非零数字”第一反应就是把阶乘一个个乘出来乘完对 10 取模。这个思路在小范围里可以但放在这道题里就是从第一步就错。1.1 为什么不能直接对 10 取模举个最简单的例子6! 等于 720去掉末尾的 0 之后是 72个位是 2。但如果边乘边取模从 1 乘到 6 的过程中一旦乘出 10、20、30 这样的“整十数”模 10 的结果就会变成 0并且后面无论再乘什么结果都会一直停在 0 上。也就是说尾部的 0 会“污染”取模结果。普通乘法取模保不住我们想要的末位非零数字因为 10 这个模数本身就包含了 0 的干扰因子。正确做法是把阶乘里的“2 因子”和“5 因子”单独拿出来考虑因为 2 × 5 10末尾 0 的本质就是这两个因子配了对。1.2 这题绝对不是让你把阶乘算出来如果题目给的 N 是 10 以内暴力算没问题。但 HDU1066 这类大数题N 通常能给出几十位甚至上百位。就算你有高精度库把 100 位的 N 的阶乘完整展开位数能达到天文数字级别内存和运行时间都顶不住。所以这题真正的门槛是不把阶乘算出来却要算出它的“去零末位”。这就需要一个数学上的化简把问题规模从 N 直接降到 N/5再降 N/25一路缩下去最后缩到可以直接查表的范围。2. 数学化简把“去零”变成一条递推这一节是整个题目的核心。理解了这里的递归关系后面的代码其实就是套模板。2.1 尾部 0 的来源与 2、5 配对为了说清楚后面的公式需要先明确一个概念。阶乘中因子 2 的数量永远多于因子 5 的数量所以 N! 尾部 0 的个数由 5 的个数决定也就是v5(N!) N/5 N/25 N/125 ...去掉所有尾部的 0实际上就是去掉 min(v2, v5) 对“2 × 5”把 v2 - v5 个剩余的 2 因子保留下来。这样一来N! 去掉所有因子 2 和 5 后剩下的部分就和 10 互质了。只有和 10 互质的数才适合做模 10 的乘法运算。上面的分析给出了方向把 N! 拆成 2^a × 5^b × C其中 C 不含 2 因子和 5 因子。最后答案等于 C × 2^(a-b) 的个位数。这里的难点是 C 本身也很大必须找出 C 的规律性。2.2 关键的递归结构N → N/5不知道大家有没有见过这种写法设 f(n) 表示 n! 去掉尾 0 后的末位数字那么有f(n) f(n/5) × table[n % 20] % 10这个式子第一次看会觉得有点暴力。为什么是 n/5为什么模 20table 表又是什么我的理解是这样的每 5 个数里至少有一个 5 的倍数这一部分会产生额外的尾 0所以要把它们单独“提取”出来递归处理这就是 n/5 的来源。去掉所有 5 的倍数之后剩下的数在模 10 下不是 5 的倍数但也包含偶数需要和 2 因子的补偿放在一起考虑。由于模 10 的乘法群中2 的幂每 4 次循环一次而和 10 互质的数在 20 个数里会呈现完整的循环节所以周期取 20 最合适。table 表就是预处理出来的 20 个值表示某个前缀贡献的乘积。这张表具体可以这样理解它不是 n! 去零末位而是配合递归公式使用的一个循环贡献表实测下来完全成立。用表的好处是不用每次递归都重新算直接把 n 对 20 取模查表得到一个贡献值再乘上 f(n/5) 即可。一个小细节需要注意为什么递归到 n0 时要返回 1因为递归到 0 意味着已经没有任何数字可乘了乘法单位元就是 1叠加上去不影响结果。2.3 先手动验几个值心里有底光看公式容易发虚我建议你拿出几个小 N 手动验一下。我把递推过程拆开写一遍f(5) f(1) × table[5] 1 × 2 2而 5! 120去零末位正好是 2f(10) f(2) × table[10] 2 × 4 8而 10! 3628800去零末位正好是 8f(20) f(4) × table[0] 4 × 1 4而 20! 2432902008176640000去零末位正好是 4f(25) f(5) × table[5] 2 × 2 4这个值有争议但实际 25! 去掉 6 个尾 0 后末位确实是 4几个例子验下来这个递推关系是稳的。后面只要把 f(n/5) 不断展开本质上就是一个 log5(N) 层的递归或迭代。3. 大数表示与字符串模除实现公式有了第二个拦路虎是大数。题目里 N 的位数可能到百位级C 的 long long 完全不够用必须用字符串或者高精度数组来处理。3.1 为什么不用 int128也不用高精度库有些选手喜欢直接用高精度模板或者 Python 的大整数。Python 确实可以直接把 N 转成 int但竞赛环境不总是允许 Python而且 C 选手面对这种字符串操作其实更通用。更重要的是这道题需要的不是完整大数四则运算只需要两种能力对一个十进制字符串除以 5对一个十进制字符串模 20只要会这两样大数问题就解决了。没必要为此搬出完整高精度类。3.2 字符串除以 5小学竖式直接搬字符串除法其实和小学竖式一模一样从左往右一位位处理维护当前余数当前余数乘以 10 加上下一位除以 5 得到商的这一位再更新余数。按照这个思路写函数很简洁// 返回 s / 5 的十进制字符串 string div5(const string s) { int rem 0; string res; for (char c : s) { int cur rem * 10 (c - 0); rem cur % 5; int q cur / 5; if (!res.empty() || q 0) { res.push_back(char(0 q)); } } if (res.empty()) { res 0; } return res; }这里有一个容易踩的坑当某一位商为 0 时不能把前导 0 也存进去否则会出现“00512”这种字符串。解决办法是用 res 是否为空来判断只有当 res 非空或者当前商 q 大于 0 时才写入。最终如果整个结果为空说明 N 是 0 或小于 5 的数直接返回字符串 0。另外提醒一句这种字符串除法的复杂度是线性的每次扫描一遍字符串后面递归多轮之后总复杂度约 O(L²)L 是 N 的位数。题目 N 才几百位完全不是问题。3.3 取模 20只需要看最后两位模 20 很简单20 能整除 4 和 5所以任何整数对 20 取模只和这个数的后两位有关。比如 123456 对 20 取模等价于 56 对 20 取模结果是 16。这个规律来自十进制数的基本性质判断一个数能否被 4 或 5 整除都只需看末位或末两位而 20 4 × 5所以模 20 也只看末两位。写成函数就是int mod20(const string s) { int n (int)s.size(); int x 0; for (int i max(0, n - 2); i n; i) { x x * 10 (s[i] - 0); } return x % 20; }注意 n 可能小于 2比如 N 是单个数字 7这时候直接从第一位开始取就行不需要额外判空。3.4 完整代码递归改成循环稳如老狗有了 div5 和 mod20主流程不需要真的递归用一个 while 循环从左往右不断除以 5 就好。因为递推公式是 f(n) f(n/5) × table[n%20]从底向上迭代时初始 ans 1每次取出当前字符串的 n%20查表乘进 ans再把字符串更新为 n/5直到字符串变成 0。完整代码长这样#include bits/stdc.h using namespace std; const int table[20] { 1, 1, 2, 6, 4, 2, 2, 4, 2, 8, 4, 4, 8, 4, 6, 8, 8, 6, 8, 2 }; string div5(const string s) { int rem 0; string res; for (char c : s) { int cur rem * 10 (c - 0); rem cur % 5; int q cur / 5; if (!res.empty() || q 0) { res.push_back(char(0 q)); } } if (res.empty()) { res 0; } return res; } int mod20(const string s) { int n (int)s.size(); int x 0; for (int i max(0, n - 2); i n; i) { x x * 10 (s[i] - 0); } return x % 20; } int lastNonZeroDigit(string n) { int ans 1; while (n ! 0) { ans ans * table[mod20(n)] % 10; n div5(n); } return ans; } int main() { string s; while (cin s) { cout lastNonZeroDigit(s) endl; } return 0; }这段代码在思路上是最朴素的实现每循环一次N 的位数减少大约 1/3因为除以 5所以循环次数大概是 log5(N)比如 N 有 500 位循环大约 300 多次每次扫描 500 位总耗时还是毫秒级。4. 周期表从哪来打表找规律不背错才是王道很多题解会直接丢出那 20 个数字看起来像魔法。这里我建议真正理解一下这张表是怎么得到的否则换个数据规模很容易表错。4.1 先暴力生成前缀再验证周期你可以先写一个程序暴力计算从 1 乘到 k 的所有数中去掉因子 5 后的数字乘积 mod 10并观察循环。实操时我是这样做的先算 1 到 200 的前缀然后对比间隔 20 的前缀积如果发现 mod 10 的结果相同说明 20 是一个循环周期。还有一种更直接的方式拿递推公式去暴力验证小 N。把小 N 的真实 N! 去零末位和查表公式的结果逐一对照只要 0 到几百都对得上那这张表就是可靠的。竞赛中这叫“打表找规律”省时省力还能避免推导出错。4.2 表项到底记录了什么table[i] 可以理解为在以 20 为周期的一个分组里前缀部分对最终答案的贡献值。它不是简单的“i! 去掉尾零末位”而是配合递归公式一起设计的。如果硬要解释可以这么说20 个数为一组2 因子的幂循环周期是 45 因子的影响由 n/5 递归承担剩余因子和 2 因子补偿合在一起模 10 正好形成一个长度为 20 的循环节。为了可读性我可以把表再列一次建议你抄下来或者自己重新打表验证i012345678910111213141516171819table[i]11264224284484688682如果你担心横着看不方便我可以直接提醒一句很多新手背这张表的时候容易把 table[10] 记成 8这是一个常见的坑。table[10] 是 4因为 20 的循环节在这里和 10! 去零末位并不一致。遇到这种容易混的值最好的办法不是强背而是用程序验证一遍。4.3 复杂度分析为什么几百位也能秒出每次 div5 都是 O(L)L 是当前字符串长度。每轮除以 5字符串长度大约除以一个小于 1 的因子。所以总复杂度是T(L) ≈ L L * (log5(10) 的倒数?)粗略看就是 O(L × log5(N))但严格说每轮长度递减最后可以看作 O(L²) 级别。L 在百位到千位之间完全轻松。就算 N 出了满分数据长度 1000整个程序也只是毫秒级不需要上任何高级优化。这个时间复杂度在同类题里相当友好。很多大数题的难点其实不在大数本身而在怎么把问题化简到只需要大数“模除”就能解决的程度。5. 实战踩坑、边界与扩展思考最后这部分是我真正想说的。网上题解一大把但第一次写这道题的人通常会踩到几个莫名其妙的坑这里列出来能省你不少时间。5.1 常见 WA 原因清单第一个高频坑是 n0 或 n1。0! 和 1! 都是 1按照递推公式n0 时查 table[0] 1n1 时查 table[1] 1循环直接结束输出 1。这个逻辑是对的但有些实现里把停止条件写成“字符串长度为 1 且字符是 0”容易写成“字符串非空”之类导致死循环或者输出 0。第二个坑是 div5 结果的前导 0。比如 N33/50如果 res 把 0 写进去了循环会一直以 0 正常结束这还好。但如果 N50div5 得到 10 正常可如果你用“忽略前导零”和“不忽略”两套逻辑不一致可能得到 10 或 010 的差异。模 20 对 010 和 10 结果一样但字符串比较 “n ! 0” 时010 不会结束导致死循环。所以 div5 一定要彻底去掉前导 0。第三个坑是输入的读取方式。题目一般给多组测试数据直到 EOF所以主循环要用 while (cin s)。如果只读单个 N就会漏掉后续数据输出结果也会少一大截。第四个坑和取模有关。递归或循环过程中 ans 乘 table 后一定要 % 10但注意中途不要提前对 10 取模取过头。因为这里的 ans 最终只要个位先 %10 再乘和乘完再 %10 结果一样但有些地方会对中间结果取模 20 或 4容易混。我的经验是统一用 long long 存只在最后取模减少出错概率。5.2 我的排查流程如果提交后 WA我一般会先拿小 N 做对拍。把暴力程序算 1 到 20 的真实阶乘去零末位和这个程序输出对比。这里有个小技巧暴力程序不需要算真正的阶乘只需要在乘法过程中不断去掉末尾 0并且只保留最后一位非零数字就能支持更大的 N 来做对拍因为模 10 的运算会保留下正确结果。对拍一旦发现某个小 N 不一致立刻检查表项是不是抄错了再检查模 20 是不是用了最后一位而不是最后两位。这两处错误占了这个题 WA 原因的八成。另外如果你在本地测试“12345678901234567890”这种长字符串肉眼很难核对结果建议直接用 Python 的 math.factorial 算一下再取去零末位作为参考值。这也提醒我们平时刷题时备一个暴力版脚本能帮大忙。5.3 从这道题延伸出来的通用技能做完这道题你收获的不只是一个 AC。至少这几个技能是通用的大数的字符串除法、字符串取模这个套路在很多大数题里都通用尤其是需要反复除以同一个小质因数的场景。因数分解下的尾零问题比如组合数 C(n, m) 末尾有多少个 0本质也是统计 5 的个数。打表找循环周期。遇到找不到数学公式的题用程序生成前缀并探测循环节是竞赛里常用的一招。把大数问题转化成“每次除以某个小常数”的迭代而不是一次大除法这样代码更简单也更容易检查。我个人在实际操作中还有一个习惯遇到这种所谓“大数 模除”的题不要急着把大数模板搬出来先看看能不能把模型化简成只对大数做少数几种运算。很多时候题目只需要“除以一个数”或者“取模一个小数”完全不需要完整的高精度。一旦看穿这一点代码量能少一半出错概率也小很多。这道题就是典型的例子核心循环只有几行剩下的全在数学化简和大数基本功上。