很多第一次接触“1173阶乘和”这道题的朋友第一反应都是“阶乘嘛谁不会”。但真上手写往往就被大数卡住了。题目本身说的就是计算 S 1! 2! 3! ... n!n 一大普通整形根本装不下这才是这道题真正想考的东西。这篇文章我把从头到尾的思路、高精度实现、踩坑记录都摊开讲适合刚刷 OJ 的新手也适合想系统整理高精度模板的选手。这道题几乎是所有算法题库里的“常青树”不管是作为大一期末的机考还是作为高精度运算的入门题出镜率都非常高。它的核心难点不在“阶乘”的数学定义而在“结果溢出”三个字。明白这一点你就会发现“阶乘和”其实是两个独立知识点的组合高精度乘法 高精度加法。搞懂了它后面遇到阶乘相关的变体题、大数累加题基本都能顺着同一套思路打下来。1. 题目拆解与整体思路1.1 题意其实很简单先明确一下输入输出。题目一般会给你一个正整数 n要求输出 1! 2! ... n! 的值。注意这里的“!”是阶乘不是感叹号。所谓 k 的阶乘就是从 1 连乘到 k 的结果比如 5! 1 × 2 × 3 × 4 × 5 120。于是当 n 5 时阶乘和就是S 1! 2! 3! 4! 5! 1 2 6 24 120 153这个 153 就是 n 5 时的输出。看这个式子你会觉得整道题似乎没有任何“科技含量”不就是循环累加吗但题目一旦把 n 放到 50、100、甚至 1000情况就完全不同了。先做个直观对比20! 2432902008176640000这个数字已经超出 64 位无符号整数的范围。n 只要到 21unsigned long long 就直接爆掉。而很多题目把 n 的范围给到 50、100 甚至更大目的就是用现实中的“装不下”来逼你写大数处理。所以这道题看似在考数学实际在考编码基本功你能不能自己动手实现一个“虽然慢一点但永远不会溢出”的大整数运算。它不是数学竞赛题里那种需要技巧的求和化简而是一道非常标准的“高精度运算”入门模板题。1.2 朴素解法到底卡在哪很多新手一上来会这么写#include iostream using namespace std; int main() { int n; cin n; long long sum 0, fac 1; for (int i 1; i n; i) { fac * i; // 计算 i! sum fac; // 累加 } cout sum endl; return 0; }这个代码看着很对逻辑上也确实没有任何问题。问题是当 i 增长到一定程度fac 这个变量就放不下了。long long 最多只能存到约 9.22 × 10^18对应 20! 是 2.43 × 10^18还能勉强装下到了 21! 就已经是 5.1 × 10^19直接溢出。溢出之后就非常难调试。你会发现 fac 可能突然变成负数或者 sum 变成一个乱码般的大数字而且不同编译器、不同机器上跑出来的结果还不一样。这个阶段你最容易怀疑人生觉得自己的数学公式推导错了。其实公式没问题是数据类型有上限而已。理解了“溢出”这个根源解决思路就很清晰了既然内置的 int、long long 装不下那我们自己用一个足够大的数组来存数字。数组的长度你可以根据 n 的范围提前开好每一位只存 0 到 9 的一个数字然后把整个数组想象成一个“超级长的整数”再去模拟手算乘法和加法的过程。这就是所谓的高精度运算。2. 高精度运算原理与选型2.1 数组存数倒着存才顺手高精度运算的第一件事就是选一个合适的存储结构。常见方案有两种一种是直接用 string 存适合处理输入就是大数的题目另一种是用 int 数组每位存一个数字下标 0 存个位、下标 1 存十位依次类推。我推荐数组倒着存。为什么倒着因为进行乘法和加法的时候我们需要从低位向高位逐位处理而进位也是从低位向高位传播的。如果正着存最高位在下标 0处理进位时就得反复移动整个数组非常麻烦。倒着存下标 0 就是个位进位直接往下标 1 推代码写起来顺手很多。举个例子数字 153 用倒序数组表示就是a[0] 3 a[1] 5 a[2] 1输出的时候只需要从数组末尾向前遍历找到第一个非 0 的位置然后倒序打印即可。注意这里有个特别容易翻车的细节如果这个数本身就是 0你得保证输出一个字符 0而不是什么都不输出。数组开多大可以用一个近似公式估算n! 的位数大约是 log10(n!) 1。手算不方便但我们可以记住几个常见值50! 大约有 65 位100! 大约有 158 位1000! 大约有 2568 位。只要题目里 n ⩽ 100开一个 200 的数组完全够用如果 n 可能到 1000开出 3000 比较稳妥。做题时别抠门数组多开一点不会超时只会让你少一个“数组越界”的坑。2.2 高精度乘法和加法模拟竖式高精度加法模拟的是小学学过的竖式加法。两个数组从低位到高位对齐逐位相加如果某一位的和大于等于 10就向高位进 1当前位保留和对 10 取模的结果。而这道题里更关键的是高精度乘法。注意我们这里算阶乘并不是“大数 × 大数”而是“大数 × 普通 int”。比如我们已经算出了 5! 120想算 6! 时只要让 120 这个大数乘以 6 就行。这种操作在竞赛里叫“高精度乘单精度”实现起来比大数乘大数简单很多。具体做法是把大数数组里的每一位都乘以这个 int得到一个临时结果然后统一处理进位。比如 120 乘以 6倒序存为 [0, 2, 1]分别是个位、十位、百位逐位乘之后得到 [0, 12, 6]这时十位上的 12 需要向百位进 1调整后变成 [0, 2, 7]也就是 720。这个处理过程用代码写出来非常短但理解这个“先乘后进位”的思路很重要它是整道题的核心之一。2.3 为什么不用现成的大数库有些读者可能会问Python 里 int 是任意精度的C 里也有 boost::multiprecision::cpp_int为什么还要手写这个问题问得很好。现实工程中我当然建议你能用库就用库省时省力。但刷题场景里手写高精度有三个不可替代的价值一是很多 OJ 的评测环境不允许你用非标准库boost 不一定会被支持你写了半天结果编译不过心态直接炸裂。二是手写高精度能让你真正理解计算机是如何表示和处理大整数的这个基本功会在你学密码学、大数分解、哈希设计时派上用场。三是面试和考试里经常明确要求“不得使用大数库”考察的就是你能否独立设计存储结构和运算逻辑。所以虽然“自己造轮子”看起来蠢但在“阶乘和”这道题里它恰恰是标准解法和唯一解法。3. 完整实现从单次阶乘到逐项累加3.1 一个高效的小技巧迭代阶乘先说说计算策略。很多人写这道题容易写成一个双重循环外层枚举 i内层从 1 乘到 i 重新算一遍阶乘。这样写没错但会有很多重复计算。更好的做法是“迭代阶乘”。因为 (i)! (i-1)! × i我们在循环里可以维护一个“当前的大数阶乘变量 fac”每轮循环只做一件事让 fac 乘以 i得到新的 i!。然后把这个新的 fac 累加到总和 sum 里。整个过程只需要一个循环时间和空间上都更优。代码的骨架大致是int n; cin n; int fac[MAXN] {0}; // 存当前阶乘倒序 int sum[MAXN] {0}; // 存阶乘和倒序 fac[0] 1; // 0! 1 for (int i 1; i n; i) { // 1. fac fac * i // 2. sum sum fac } // 3. 倒序输出 sum这样就把“计算阶乘”和“累加”解耦了。每一步的 fac 都是正确的 i!不需要每次从头重新乘一遍。这个优化在 n 很大时能显著减少常数虽然从理论上复杂度阶没变但常数小就是快。3.2 完整代码与关键函数说明下面我给出一份完整的 C 实现。这份代码我做了充分的注释方便你对照理解。#include iostream #include cstring using namespace std; const int MAXN 500; // 数组长度根据 n 的范围调整 // 高精度乘法a a * x其中 x 是普通整数 void mul(int a[], int x) { int carry 0; for (int i 0; i MAXN; i) { int cur a[i] * x carry; a[i] cur % 10; carry cur / 10; } } // 高精度加法a a b要求 a 和 b 都是倒序存储 void add(int a[], int b[]) { int carry 0; for (int i 0; i MAXN; i) { int cur a[i] b[i] carry; a[i] cur % 10; carry cur / 10; } } // 从数组输出结果跳过前导 0 void print(int a[]) { int i MAXN - 1; while (i 0 a[i] 0) i--; for (; i 0; i--) { cout a[i]; } cout endl; } int main() { int n; cin n; int fac[MAXN] {0}; // 当前阶乘值 int sum[MAXN] {0}; // 最终的阶乘和 fac[0] 1; // 0! 1 for (int i 1; i n; i) { mul(fac, i); // fac i! add(sum, fac); // sum fac } print(sum); return 0; }三个函数分别负责乘、加、输出。你可能注意到 mul 和 add 函数的代码非常相似都是逐位处理加进位。实际上高精度加法和乘单精度的核心逻辑确实是同一个套路。区别仅在于乘法中每一位的“增量”来源于乘积而加法中来源于两个数组对应位相加。3.3 手算推演n 5 时发生了什么我特别建议大家在看代码的同时自己拿一张纸跟着推一遍。我们模拟一下 n 5 时程序内部的状态初始状态fac [1, 0, 0, ...]sum [0, 0, 0, ...]i 1mul(fac, 1)fac 变成 [1, 0, 0, ...]add(sum, fac)sum [1, 0, 0, ...]i 2mul(fac, 2)fac [2, 0, 0, ...]add(sum, fac)sum [3, 0, 0, ...]i 3mul(fac, 3)这里注意了fac 原先是 2每一位乘 3 后得到 [6, 0, 0, ...]add(sum, fac)sum [9, 0, 0, ...]i 4mul(fac, 4)3! 6乘以 4 后得到 [4, 2, 0, ...]也就是 24add(sum, fac)sum [3, 3, 1, ...]也就是 33i 5mul(fac, 5)4! 24乘以 5 后得到 [0, 2, 1, ...]也就是 120add(sum, fac)sum [3, 5, 1, ...]也就是 153最终输出 153和手算一致。你看整个过程中 fac 一直准确地保存着上一个阶乘的值sum 则逐步累加。这种“滚动更新”的思路不仅适合这道题也适合很多递推类大数题。3.4 数组长度与位数的取舍关于 MAXN 的取值我再多说两句。有的朋友会觉得 500 太大了内存浪费。其实在这种 OJ 题里一个 int 数组开 500 长度也就 2000 字节完全无所谓。真正需要注意的反而是“开小了”。假设题目 n 最大为 100100! 的位数是 158那么数组长度至少大于 158。最稳妥的方案是先估算一个上限再加一倍余量。如果 n 的范围没有明确告诉你宁可在代码开头把 MAXN 定义得大一些比如 1000 或 5000也不要让它越界。还有一个高级玩法是“压位存储”。把数组每一位存 0 到 9999而不是 0 到 9这样每一位能表示 4 个十进制位数组长度可以缩短到原来的四分之一运算速度也能提升不少。不过压位会带来一个麻烦输出时需要对中间位补 0比如数组某个位置上存的是 12你输出时得补成“0012”。这道题数据规模一般不大不压位也完全可以过压位可以作为进阶练习自己尝试。4. 实测效果与复杂度分析4.1 不同 n 下的表现为了让大家有一个直观感受我实际跑了一下代码记录了不同 n 下的输出位数和运行表现n阶乘和的结果位数直观感受107秒出几乎无感知2019秒出long long 极限附近5065秒出高精度开始展示威力100158秒出所有计算瞬间完成200375秒出无压力10002568依然能秒出但循环次数明显增加这个结果说明对绝大多数竞赛数据手写高精度完全不虚。很多人以为高精度一定慢其实它慢是相对“内置整数运算”而言的因为每一位都得用循环去处理。但只要数组长度控制在几千以内单次运算也就几千次操作整体跑完也不过百万级现代 CPU 处理起来毫无压力。4.2 时间复杂度拆解我们仔细分析一下复杂度。外层循环从 1 跑到 n一共 n 次。每次循环里mul 函数遍历整个数组复杂度是 O(MAXN)。add 函数同样是 O(MAXN)。所以总时间复杂度为 O(n × MAXN)。如果 MAXN 和 n 同量级例如 n 100 时 MAXN 需要开到约 200那么总复杂度约为 O(n²) 级别也就是大约 10^4 次操作。如果 n 1000MAXN 约 3000操作次数约 3 × 10^6依然是现代计算机可以轻松承受的范围。空间复杂度则是 O(MAXN)主要占用是两个数组 fac 和 sum外加常数空间没有任何递归和动态分配非常友好。我们也可以进一步优化常数比如 mul 函数的循环可以只在“当前已知的最高位”范围内进行而不是每次都跑满 MAXN。只要额外记录一个 len 表示 fac 的有效位数循环里 i len 即可算式结果位数变长时再更新 len。类似地add 函数也可以记录 sum 的有效位数。这样能减少一半左右的无效计算不过对于这道题来说属于“锦上添花”不是必需。4.3 与内置整型的边界对比这里值得记一个经验值unsigned long long 能安全计算的阶乘范围是 20!再多一位“21!”就开始溢出。如果你用 long long同样到 20! 就逼近极限。所以当题目给你 n 的输入范围超过 20 时直接默认必须使用高精度不要抱着“试试 long long 能不能过”的侥幸心理。另外有些题目会在“阶乘和”外面再加一个取模操作比如要求对 10007 取模。一旦出现取模情况又变了你可以用“边乘边模”的方法把每一步结果都限制在模数以内这时候 long long 就完全够用。但要注意的是取模后的累加优先级和正常情况一样仍然是先算阶乘再累加再取模你可以把取模运算“放”到每一步中因为 (a × b) mod m ((a mod m) × (b mod m)) mod m这是另一个经典题目变体后面我会再展开。5. 常见问题与排查技巧实录5.1 数组越界或长度不够这是高精度题最容易犯的错误而且它往往不是“报错”而是“结果莫名不对”。比如你把 MAXN 开到 200但是 n 100 时 100! 的位数是 158理论上没问题可一旦题目数据升级到 n 200100! 位数为 375直接就越界了。越界之后数组后面的数据会被覆盖产生一些非常诡异的输出比如莫名其妙的 0、中间的乱码数字、时对时错很难排查。排查技巧在输出之前用另一个变量跟踪数组的有效长度。你可以在 add 和 mul 函数里记录“历史最高位”每次进位后更新这个值。只要保证历史最高位不超过 MAXN就不会越界。更省心的做法是把 MAXN 开成一个较大的固定值比如 2000并配合“有效位数”变量一起用。5.2 进位顺序与方向错误进位处理是高精度运算里另一个经典翻车点。初学者经常把乘法和加法的进位逻辑混在一起或者在循环内直接修改当前位导致进位“提前被使用”。正确做法是第一步先对每一位执行乘法或加法得到一个临时值第二步再把这个临时值分解为“留在当前位的余数”和“进到高位的进位”。千万不要一边算当前位一边把进位加到下一位上面去那个进位应该是下一步循环才处理的否则会出现重复相加的 bug。一个具体的反面案例“fac[i1] carry”写在“fac[i] cur % 10”之前这其实也行但容易造成逻辑混乱。我建议统一写成“先算 cur a[i] * x carry再赋值 cur % 10最后 carry cur / 10”这种写法把进位传播封装在循环里最不容易出错。5.3 输出顺序与 0 的处理输出顺序错误是另一个高频问题。因为我们存储时是倒序的输出时就要从数组末尾往前找第一个非 0 位置然后从这个位置开始倒着输出。很多新手直接把数组从前往后输出结果把一个 153 输出成 351完全不对。尤其要注意的是“结果为 0”的情况。比如题目允许 n 0那么 0! 1阶乘和 S 1输出应该是 1。如果 n 0 时你没有正确初始化或者输出函数里把所有 0 都跳过去了就会输出一个空串白白丢分。最好在 print 函数里加一个保护如果整个数组全是 0就输出一个字符“0”。5.4 循环边界i 从 1 还是从 0 开始阶乘定义为 0! 11! 1。所以很多实现都选择从 1 开始循环这没有问题。但如果你的题目输入可能为 0请一定在循环前把 fac 初始化为 1并且不要进入循环直接输出 1。还有种常见写法是循环从 2 开始先把 sum 和 fac 都设为 1因为 1! 1然后从 i 2 开始跑。这样做也能加快一点点速度但要注意“初始化为 1”这一步和“输出到底有几个 1”的对应关系少加一个 1 或者多加一个 1 都会导致答案错误。我个人的习惯是“从 1 开始循环让代码语义和数学定义完全对应”这样可以极大减少出错概率。5.5 忘记复用变量或错误复用有些同学会写一个专门的函数来计算 i 的阶乘然后累加。这个思路没问题但如果不小心把 fac 数组复用到“每次调用都重新计算”复杂度会变成 O(n² × MAXN)在 n 稍大时很容易超时。这时候你写的是“正确的答案但过不了题”非常可惜。我的建议是用迭代更新的方式维护一个全局的 fac。这样代码不仅简洁而且性能好。一旦你养成了“用空间换时间”的习惯后面遇到递推类题目比如斐波那契数列的大数版、排列组合大数版都会顺手很多。5.6 常见错误速查表症状可能原因解决方案结果变成负数或乱码使用了 int/long long 存储溢出改用数组高精度输出结果颠倒输出时没有从高位开始先找最高非 0 位再倒序输出结果少了一位比如 153 输出 53最高位被进位覆盖或数组越界检查进位逻辑和数组长度数字中间出现奇怪的 0进位没有正确传播检查 mul/add 中的进位顺序结果总是 1循环从 0 开始导致每次都只加了 1检查循环边界确保从 1 开始结果巨大且稳定但不正确数组长度不够高位数据丢失增大 MAXN或启用长度记录变量编译不通过提示数组长度不够定义的数组维度过大或使用了非常量用 const int 定义 MAXN这张表建议收藏起来以后刷任何高精度题都能用上。6. 扩展思考从阶乘和到更广的应用6.1 大型阶乘题与压位优化“阶乘和”本身是一道入门题但它的思想可以延伸出无数变体。最常见的变体是直接求 n! 的值这个时候你就不需要累加 sum 了只需要循环调用 mul 函数。另一个变体是求阶乘和的后 k 位此时可以结合“取模”和“滚动数组”一起实现复杂度也能压得更低。当 n 上升到 10000 甚至 100000 时基础的高精度可能不够快就需要压位或分治优化。压位的思路前面提到过把数组每个元素从存 0-9 变成存 0-9999这样数组长度缩短到原来的四分之一乘法中循环次数也同步减少。进阶一点的方案是使用 FFT快速傅里叶变换做高精度乘法能把大数乘法的复杂度从 O(n²) 降到 O(n log n)不过这已经远超“阶乘和”的要求属于另一个专题了。6.2 取模版阶乘和大数变小数有些题目会在阶乘和后面加一句“结果对 1000000007 取模”。这种题看着像高精度其实完全不需要。因为取模运算对乘法和加法都有分配律我们可以在每一步都取模中间结果不会超过模数的平方long long 完全装得下。模板代码如下const long long MOD 1000000007; long long fac 1, sum 0; for (int i 1; i n; i) { fac fac * i % MOD; sum (sum fac) % MOD; } cout sum endl;这段代码比高精度版本快了非常多因为所有运算都是 O(1) 的。但注意它只在“取模输出”的题目里有效如果题目要求输出完整精确值取模版就是错的。拿到题目先看清条件再决定选用哪种方案。6.3 在工程中的影子你可能觉得“手写大整数”只存在于竞赛和考试中现实工作完全用不到。但实际上很多基础库的底层就包含类似逻辑。比如密码学中处理超大素数的乘法、区块链中哈希值的拼接、科学计算中的任意精度浮点数都和“高精度数组 竖式运算”高度相关。理解了大数存储和进位传播你再去看一些开源大数库的源码时会发现自己能更快读懂它们的设计思路。比如它们会先把十进制转成二进制或十六进制处理因为 CPU 对 2 的幂进制天然友好或者会使用 32 位整数存储“数字块”再用类似竖式的方法做乘法。这些设计听起来高级但核心思想和你在这道题里用的数组模拟一模一样。6.4 题目变体汇总“阶乘和”有一个庞大的题目家族刷题时你会反复遇到类似风格变体核心考点难度求 n!高精度乘单精度简单求 1! 2! ... n!高精度乘 高精度加入门求 n! 末尾 0 的个数数论因子分解不用高精度中等对 M 取模的阶乘和同余运算优化简单求阶乘和的约数个数高精度 质因数分解较难大数阶乘相减高精度减 借位入门看到没有一旦掌握高精度加减乘你就等于解锁了“大整数”这个技能树后面很多问题都只是在这个基础上换壳而已。所以我建议你别只是看这篇博文而是亲手把代码敲一遍再改造成“只求 n!”、“求前 n 项阶乘和”的多个版本确保每个函数你都能随时写出来。我个人在实际操作中的体会是高精度题最忌“眼高手低”。你看代码觉得每一句都很简单但闭卷写一遍就会发现各种细节问题数组初始化有没有写、进位变量有没有归零、输出函数有没有处理全是 0 的情况。这些坑只有亲手踩过才能真正记住。最后再分享一个小技巧如果你用的是 C可以试试在本地自己写一个简单的随机数据生成器然后用 Python 内置大整数作为标准答案随机生成一堆 n对比你的程序输出。这样能在几秒钟内帮你发现各种隐蔽 bug。这个方法我几乎用在所有高精度题上实测下来非常稳能省下大量提交 WAWrong Answer后调试的时间。
高精度运算入门：1173阶乘和如何突破大数溢出？
很多第一次接触“1173阶乘和”这道题的朋友第一反应都是“阶乘嘛谁不会”。但真上手写往往就被大数卡住了。题目本身说的就是计算 S 1! 2! 3! ... n!n 一大普通整形根本装不下这才是这道题真正想考的东西。这篇文章我把从头到尾的思路、高精度实现、踩坑记录都摊开讲适合刚刷 OJ 的新手也适合想系统整理高精度模板的选手。这道题几乎是所有算法题库里的“常青树”不管是作为大一期末的机考还是作为高精度运算的入门题出镜率都非常高。它的核心难点不在“阶乘”的数学定义而在“结果溢出”三个字。明白这一点你就会发现“阶乘和”其实是两个独立知识点的组合高精度乘法 高精度加法。搞懂了它后面遇到阶乘相关的变体题、大数累加题基本都能顺着同一套思路打下来。1. 题目拆解与整体思路1.1 题意其实很简单先明确一下输入输出。题目一般会给你一个正整数 n要求输出 1! 2! ... n! 的值。注意这里的“!”是阶乘不是感叹号。所谓 k 的阶乘就是从 1 连乘到 k 的结果比如 5! 1 × 2 × 3 × 4 × 5 120。于是当 n 5 时阶乘和就是S 1! 2! 3! 4! 5! 1 2 6 24 120 153这个 153 就是 n 5 时的输出。看这个式子你会觉得整道题似乎没有任何“科技含量”不就是循环累加吗但题目一旦把 n 放到 50、100、甚至 1000情况就完全不同了。先做个直观对比20! 2432902008176640000这个数字已经超出 64 位无符号整数的范围。n 只要到 21unsigned long long 就直接爆掉。而很多题目把 n 的范围给到 50、100 甚至更大目的就是用现实中的“装不下”来逼你写大数处理。所以这道题看似在考数学实际在考编码基本功你能不能自己动手实现一个“虽然慢一点但永远不会溢出”的大整数运算。它不是数学竞赛题里那种需要技巧的求和化简而是一道非常标准的“高精度运算”入门模板题。1.2 朴素解法到底卡在哪很多新手一上来会这么写#include iostream using namespace std; int main() { int n; cin n; long long sum 0, fac 1; for (int i 1; i n; i) { fac * i; // 计算 i! sum fac; // 累加 } cout sum endl; return 0; }这个代码看着很对逻辑上也确实没有任何问题。问题是当 i 增长到一定程度fac 这个变量就放不下了。long long 最多只能存到约 9.22 × 10^18对应 20! 是 2.43 × 10^18还能勉强装下到了 21! 就已经是 5.1 × 10^19直接溢出。溢出之后就非常难调试。你会发现 fac 可能突然变成负数或者 sum 变成一个乱码般的大数字而且不同编译器、不同机器上跑出来的结果还不一样。这个阶段你最容易怀疑人生觉得自己的数学公式推导错了。其实公式没问题是数据类型有上限而已。理解了“溢出”这个根源解决思路就很清晰了既然内置的 int、long long 装不下那我们自己用一个足够大的数组来存数字。数组的长度你可以根据 n 的范围提前开好每一位只存 0 到 9 的一个数字然后把整个数组想象成一个“超级长的整数”再去模拟手算乘法和加法的过程。这就是所谓的高精度运算。2. 高精度运算原理与选型2.1 数组存数倒着存才顺手高精度运算的第一件事就是选一个合适的存储结构。常见方案有两种一种是直接用 string 存适合处理输入就是大数的题目另一种是用 int 数组每位存一个数字下标 0 存个位、下标 1 存十位依次类推。我推荐数组倒着存。为什么倒着因为进行乘法和加法的时候我们需要从低位向高位逐位处理而进位也是从低位向高位传播的。如果正着存最高位在下标 0处理进位时就得反复移动整个数组非常麻烦。倒着存下标 0 就是个位进位直接往下标 1 推代码写起来顺手很多。举个例子数字 153 用倒序数组表示就是a[0] 3 a[1] 5 a[2] 1输出的时候只需要从数组末尾向前遍历找到第一个非 0 的位置然后倒序打印即可。注意这里有个特别容易翻车的细节如果这个数本身就是 0你得保证输出一个字符 0而不是什么都不输出。数组开多大可以用一个近似公式估算n! 的位数大约是 log10(n!) 1。手算不方便但我们可以记住几个常见值50! 大约有 65 位100! 大约有 158 位1000! 大约有 2568 位。只要题目里 n ⩽ 100开一个 200 的数组完全够用如果 n 可能到 1000开出 3000 比较稳妥。做题时别抠门数组多开一点不会超时只会让你少一个“数组越界”的坑。2.2 高精度乘法和加法模拟竖式高精度加法模拟的是小学学过的竖式加法。两个数组从低位到高位对齐逐位相加如果某一位的和大于等于 10就向高位进 1当前位保留和对 10 取模的结果。而这道题里更关键的是高精度乘法。注意我们这里算阶乘并不是“大数 × 大数”而是“大数 × 普通 int”。比如我们已经算出了 5! 120想算 6! 时只要让 120 这个大数乘以 6 就行。这种操作在竞赛里叫“高精度乘单精度”实现起来比大数乘大数简单很多。具体做法是把大数数组里的每一位都乘以这个 int得到一个临时结果然后统一处理进位。比如 120 乘以 6倒序存为 [0, 2, 1]分别是个位、十位、百位逐位乘之后得到 [0, 12, 6]这时十位上的 12 需要向百位进 1调整后变成 [0, 2, 7]也就是 720。这个处理过程用代码写出来非常短但理解这个“先乘后进位”的思路很重要它是整道题的核心之一。2.3 为什么不用现成的大数库有些读者可能会问Python 里 int 是任意精度的C 里也有 boost::multiprecision::cpp_int为什么还要手写这个问题问得很好。现实工程中我当然建议你能用库就用库省时省力。但刷题场景里手写高精度有三个不可替代的价值一是很多 OJ 的评测环境不允许你用非标准库boost 不一定会被支持你写了半天结果编译不过心态直接炸裂。二是手写高精度能让你真正理解计算机是如何表示和处理大整数的这个基本功会在你学密码学、大数分解、哈希设计时派上用场。三是面试和考试里经常明确要求“不得使用大数库”考察的就是你能否独立设计存储结构和运算逻辑。所以虽然“自己造轮子”看起来蠢但在“阶乘和”这道题里它恰恰是标准解法和唯一解法。3. 完整实现从单次阶乘到逐项累加3.1 一个高效的小技巧迭代阶乘先说说计算策略。很多人写这道题容易写成一个双重循环外层枚举 i内层从 1 乘到 i 重新算一遍阶乘。这样写没错但会有很多重复计算。更好的做法是“迭代阶乘”。因为 (i)! (i-1)! × i我们在循环里可以维护一个“当前的大数阶乘变量 fac”每轮循环只做一件事让 fac 乘以 i得到新的 i!。然后把这个新的 fac 累加到总和 sum 里。整个过程只需要一个循环时间和空间上都更优。代码的骨架大致是int n; cin n; int fac[MAXN] {0}; // 存当前阶乘倒序 int sum[MAXN] {0}; // 存阶乘和倒序 fac[0] 1; // 0! 1 for (int i 1; i n; i) { // 1. fac fac * i // 2. sum sum fac } // 3. 倒序输出 sum这样就把“计算阶乘”和“累加”解耦了。每一步的 fac 都是正确的 i!不需要每次从头重新乘一遍。这个优化在 n 很大时能显著减少常数虽然从理论上复杂度阶没变但常数小就是快。3.2 完整代码与关键函数说明下面我给出一份完整的 C 实现。这份代码我做了充分的注释方便你对照理解。#include iostream #include cstring using namespace std; const int MAXN 500; // 数组长度根据 n 的范围调整 // 高精度乘法a a * x其中 x 是普通整数 void mul(int a[], int x) { int carry 0; for (int i 0; i MAXN; i) { int cur a[i] * x carry; a[i] cur % 10; carry cur / 10; } } // 高精度加法a a b要求 a 和 b 都是倒序存储 void add(int a[], int b[]) { int carry 0; for (int i 0; i MAXN; i) { int cur a[i] b[i] carry; a[i] cur % 10; carry cur / 10; } } // 从数组输出结果跳过前导 0 void print(int a[]) { int i MAXN - 1; while (i 0 a[i] 0) i--; for (; i 0; i--) { cout a[i]; } cout endl; } int main() { int n; cin n; int fac[MAXN] {0}; // 当前阶乘值 int sum[MAXN] {0}; // 最终的阶乘和 fac[0] 1; // 0! 1 for (int i 1; i n; i) { mul(fac, i); // fac i! add(sum, fac); // sum fac } print(sum); return 0; }三个函数分别负责乘、加、输出。你可能注意到 mul 和 add 函数的代码非常相似都是逐位处理加进位。实际上高精度加法和乘单精度的核心逻辑确实是同一个套路。区别仅在于乘法中每一位的“增量”来源于乘积而加法中来源于两个数组对应位相加。3.3 手算推演n 5 时发生了什么我特别建议大家在看代码的同时自己拿一张纸跟着推一遍。我们模拟一下 n 5 时程序内部的状态初始状态fac [1, 0, 0, ...]sum [0, 0, 0, ...]i 1mul(fac, 1)fac 变成 [1, 0, 0, ...]add(sum, fac)sum [1, 0, 0, ...]i 2mul(fac, 2)fac [2, 0, 0, ...]add(sum, fac)sum [3, 0, 0, ...]i 3mul(fac, 3)这里注意了fac 原先是 2每一位乘 3 后得到 [6, 0, 0, ...]add(sum, fac)sum [9, 0, 0, ...]i 4mul(fac, 4)3! 6乘以 4 后得到 [4, 2, 0, ...]也就是 24add(sum, fac)sum [3, 3, 1, ...]也就是 33i 5mul(fac, 5)4! 24乘以 5 后得到 [0, 2, 1, ...]也就是 120add(sum, fac)sum [3, 5, 1, ...]也就是 153最终输出 153和手算一致。你看整个过程中 fac 一直准确地保存着上一个阶乘的值sum 则逐步累加。这种“滚动更新”的思路不仅适合这道题也适合很多递推类大数题。3.4 数组长度与位数的取舍关于 MAXN 的取值我再多说两句。有的朋友会觉得 500 太大了内存浪费。其实在这种 OJ 题里一个 int 数组开 500 长度也就 2000 字节完全无所谓。真正需要注意的反而是“开小了”。假设题目 n 最大为 100100! 的位数是 158那么数组长度至少大于 158。最稳妥的方案是先估算一个上限再加一倍余量。如果 n 的范围没有明确告诉你宁可在代码开头把 MAXN 定义得大一些比如 1000 或 5000也不要让它越界。还有一个高级玩法是“压位存储”。把数组每一位存 0 到 9999而不是 0 到 9这样每一位能表示 4 个十进制位数组长度可以缩短到原来的四分之一运算速度也能提升不少。不过压位会带来一个麻烦输出时需要对中间位补 0比如数组某个位置上存的是 12你输出时得补成“0012”。这道题数据规模一般不大不压位也完全可以过压位可以作为进阶练习自己尝试。4. 实测效果与复杂度分析4.1 不同 n 下的表现为了让大家有一个直观感受我实际跑了一下代码记录了不同 n 下的输出位数和运行表现n阶乘和的结果位数直观感受107秒出几乎无感知2019秒出long long 极限附近5065秒出高精度开始展示威力100158秒出所有计算瞬间完成200375秒出无压力10002568依然能秒出但循环次数明显增加这个结果说明对绝大多数竞赛数据手写高精度完全不虚。很多人以为高精度一定慢其实它慢是相对“内置整数运算”而言的因为每一位都得用循环去处理。但只要数组长度控制在几千以内单次运算也就几千次操作整体跑完也不过百万级现代 CPU 处理起来毫无压力。4.2 时间复杂度拆解我们仔细分析一下复杂度。外层循环从 1 跑到 n一共 n 次。每次循环里mul 函数遍历整个数组复杂度是 O(MAXN)。add 函数同样是 O(MAXN)。所以总时间复杂度为 O(n × MAXN)。如果 MAXN 和 n 同量级例如 n 100 时 MAXN 需要开到约 200那么总复杂度约为 O(n²) 级别也就是大约 10^4 次操作。如果 n 1000MAXN 约 3000操作次数约 3 × 10^6依然是现代计算机可以轻松承受的范围。空间复杂度则是 O(MAXN)主要占用是两个数组 fac 和 sum外加常数空间没有任何递归和动态分配非常友好。我们也可以进一步优化常数比如 mul 函数的循环可以只在“当前已知的最高位”范围内进行而不是每次都跑满 MAXN。只要额外记录一个 len 表示 fac 的有效位数循环里 i len 即可算式结果位数变长时再更新 len。类似地add 函数也可以记录 sum 的有效位数。这样能减少一半左右的无效计算不过对于这道题来说属于“锦上添花”不是必需。4.3 与内置整型的边界对比这里值得记一个经验值unsigned long long 能安全计算的阶乘范围是 20!再多一位“21!”就开始溢出。如果你用 long long同样到 20! 就逼近极限。所以当题目给你 n 的输入范围超过 20 时直接默认必须使用高精度不要抱着“试试 long long 能不能过”的侥幸心理。另外有些题目会在“阶乘和”外面再加一个取模操作比如要求对 10007 取模。一旦出现取模情况又变了你可以用“边乘边模”的方法把每一步结果都限制在模数以内这时候 long long 就完全够用。但要注意的是取模后的累加优先级和正常情况一样仍然是先算阶乘再累加再取模你可以把取模运算“放”到每一步中因为 (a × b) mod m ((a mod m) × (b mod m)) mod m这是另一个经典题目变体后面我会再展开。5. 常见问题与排查技巧实录5.1 数组越界或长度不够这是高精度题最容易犯的错误而且它往往不是“报错”而是“结果莫名不对”。比如你把 MAXN 开到 200但是 n 100 时 100! 的位数是 158理论上没问题可一旦题目数据升级到 n 200100! 位数为 375直接就越界了。越界之后数组后面的数据会被覆盖产生一些非常诡异的输出比如莫名其妙的 0、中间的乱码数字、时对时错很难排查。排查技巧在输出之前用另一个变量跟踪数组的有效长度。你可以在 add 和 mul 函数里记录“历史最高位”每次进位后更新这个值。只要保证历史最高位不超过 MAXN就不会越界。更省心的做法是把 MAXN 开成一个较大的固定值比如 2000并配合“有效位数”变量一起用。5.2 进位顺序与方向错误进位处理是高精度运算里另一个经典翻车点。初学者经常把乘法和加法的进位逻辑混在一起或者在循环内直接修改当前位导致进位“提前被使用”。正确做法是第一步先对每一位执行乘法或加法得到一个临时值第二步再把这个临时值分解为“留在当前位的余数”和“进到高位的进位”。千万不要一边算当前位一边把进位加到下一位上面去那个进位应该是下一步循环才处理的否则会出现重复相加的 bug。一个具体的反面案例“fac[i1] carry”写在“fac[i] cur % 10”之前这其实也行但容易造成逻辑混乱。我建议统一写成“先算 cur a[i] * x carry再赋值 cur % 10最后 carry cur / 10”这种写法把进位传播封装在循环里最不容易出错。5.3 输出顺序与 0 的处理输出顺序错误是另一个高频问题。因为我们存储时是倒序的输出时就要从数组末尾往前找第一个非 0 位置然后从这个位置开始倒着输出。很多新手直接把数组从前往后输出结果把一个 153 输出成 351完全不对。尤其要注意的是“结果为 0”的情况。比如题目允许 n 0那么 0! 1阶乘和 S 1输出应该是 1。如果 n 0 时你没有正确初始化或者输出函数里把所有 0 都跳过去了就会输出一个空串白白丢分。最好在 print 函数里加一个保护如果整个数组全是 0就输出一个字符“0”。5.4 循环边界i 从 1 还是从 0 开始阶乘定义为 0! 11! 1。所以很多实现都选择从 1 开始循环这没有问题。但如果你的题目输入可能为 0请一定在循环前把 fac 初始化为 1并且不要进入循环直接输出 1。还有种常见写法是循环从 2 开始先把 sum 和 fac 都设为 1因为 1! 1然后从 i 2 开始跑。这样做也能加快一点点速度但要注意“初始化为 1”这一步和“输出到底有几个 1”的对应关系少加一个 1 或者多加一个 1 都会导致答案错误。我个人的习惯是“从 1 开始循环让代码语义和数学定义完全对应”这样可以极大减少出错概率。5.5 忘记复用变量或错误复用有些同学会写一个专门的函数来计算 i 的阶乘然后累加。这个思路没问题但如果不小心把 fac 数组复用到“每次调用都重新计算”复杂度会变成 O(n² × MAXN)在 n 稍大时很容易超时。这时候你写的是“正确的答案但过不了题”非常可惜。我的建议是用迭代更新的方式维护一个全局的 fac。这样代码不仅简洁而且性能好。一旦你养成了“用空间换时间”的习惯后面遇到递推类题目比如斐波那契数列的大数版、排列组合大数版都会顺手很多。5.6 常见错误速查表症状可能原因解决方案结果变成负数或乱码使用了 int/long long 存储溢出改用数组高精度输出结果颠倒输出时没有从高位开始先找最高非 0 位再倒序输出结果少了一位比如 153 输出 53最高位被进位覆盖或数组越界检查进位逻辑和数组长度数字中间出现奇怪的 0进位没有正确传播检查 mul/add 中的进位顺序结果总是 1循环从 0 开始导致每次都只加了 1检查循环边界确保从 1 开始结果巨大且稳定但不正确数组长度不够高位数据丢失增大 MAXN或启用长度记录变量编译不通过提示数组长度不够定义的数组维度过大或使用了非常量用 const int 定义 MAXN这张表建议收藏起来以后刷任何高精度题都能用上。6. 扩展思考从阶乘和到更广的应用6.1 大型阶乘题与压位优化“阶乘和”本身是一道入门题但它的思想可以延伸出无数变体。最常见的变体是直接求 n! 的值这个时候你就不需要累加 sum 了只需要循环调用 mul 函数。另一个变体是求阶乘和的后 k 位此时可以结合“取模”和“滚动数组”一起实现复杂度也能压得更低。当 n 上升到 10000 甚至 100000 时基础的高精度可能不够快就需要压位或分治优化。压位的思路前面提到过把数组每个元素从存 0-9 变成存 0-9999这样数组长度缩短到原来的四分之一乘法中循环次数也同步减少。进阶一点的方案是使用 FFT快速傅里叶变换做高精度乘法能把大数乘法的复杂度从 O(n²) 降到 O(n log n)不过这已经远超“阶乘和”的要求属于另一个专题了。6.2 取模版阶乘和大数变小数有些题目会在阶乘和后面加一句“结果对 1000000007 取模”。这种题看着像高精度其实完全不需要。因为取模运算对乘法和加法都有分配律我们可以在每一步都取模中间结果不会超过模数的平方long long 完全装得下。模板代码如下const long long MOD 1000000007; long long fac 1, sum 0; for (int i 1; i n; i) { fac fac * i % MOD; sum (sum fac) % MOD; } cout sum endl;这段代码比高精度版本快了非常多因为所有运算都是 O(1) 的。但注意它只在“取模输出”的题目里有效如果题目要求输出完整精确值取模版就是错的。拿到题目先看清条件再决定选用哪种方案。6.3 在工程中的影子你可能觉得“手写大整数”只存在于竞赛和考试中现实工作完全用不到。但实际上很多基础库的底层就包含类似逻辑。比如密码学中处理超大素数的乘法、区块链中哈希值的拼接、科学计算中的任意精度浮点数都和“高精度数组 竖式运算”高度相关。理解了大数存储和进位传播你再去看一些开源大数库的源码时会发现自己能更快读懂它们的设计思路。比如它们会先把十进制转成二进制或十六进制处理因为 CPU 对 2 的幂进制天然友好或者会使用 32 位整数存储“数字块”再用类似竖式的方法做乘法。这些设计听起来高级但核心思想和你在这道题里用的数组模拟一模一样。6.4 题目变体汇总“阶乘和”有一个庞大的题目家族刷题时你会反复遇到类似风格变体核心考点难度求 n!高精度乘单精度简单求 1! 2! ... n!高精度乘 高精度加入门求 n! 末尾 0 的个数数论因子分解不用高精度中等对 M 取模的阶乘和同余运算优化简单求阶乘和的约数个数高精度 质因数分解较难大数阶乘相减高精度减 借位入门看到没有一旦掌握高精度加减乘你就等于解锁了“大整数”这个技能树后面很多问题都只是在这个基础上换壳而已。所以我建议你别只是看这篇博文而是亲手把代码敲一遍再改造成“只求 n!”、“求前 n 项阶乘和”的多个版本确保每个函数你都能随时写出来。我个人在实际操作中的体会是高精度题最忌“眼高手低”。你看代码觉得每一句都很简单但闭卷写一遍就会发现各种细节问题数组初始化有没有写、进位变量有没有归零、输出函数有没有处理全是 0 的情况。这些坑只有亲手踩过才能真正记住。最后再分享一个小技巧如果你用的是 C可以试试在本地自己写一个简单的随机数据生成器然后用 Python 内置大整数作为标准答案随机生成一堆 n对比你的程序输出。这样能在几秒钟内帮你发现各种隐蔽 bug。这个方法我几乎用在所有高精度题上实测下来非常稳能省下大量提交 WAWrong Answer后调试的时间。
