如果你刷过信息学奥赛的题目对“1173阶乘和”这个编号大概率不陌生。光看题面阶乘、求和两个for循环叠起来就完事简单到让人觉得是来送分的热身题。但等你真的提交之后WA、RE、莫名其妙的大负数轮番上阵才反应过来这不是递归和循环的问题而是结果的位数已经远远超出了int和long long能装下的范围。这篇文章就围绕这道经典题把阶乘和从暴力循环到高精度实现、从边界测试到变式优化完整拆给你看适合刚接触高精度计算的初学者也适合想复习大数处理细节的竞赛党。我最早刷到这一题时是在一本通的高精度章节里。当时没用任何技巧直接long longn20还没事n21答案就开始变负数那种脑袋发懵的感觉我现在还记得。所以这篇文章不只是贴一份AC代码更想把“为什么必须用高精度”“高精度究竟在模拟什么”讲明白。很多同学遇到阶乘和第一反应是“算不出来就换更大类型”换成unsigned long long再不行就long double其实都绕开了本质计算机能直接表示的数字范围是有限的而阶乘的增长速度远远超出普通变量能承载的规模。1. 一道入门题为什么会出现在高精度章节里1.1 题目描述和样例这题的题面在很多在线评测系统上都能看到常见版本是输入一个正整数n求 S 1! 2! 3! … n! 的值并输出S。n的范围不同平台略有差异经典一本通版本给的是n 100有些地方会给n 50但无论哪一种都远远超过普通整数类型能直接装下的上限。先看一个最简单的例子如果输入3那么1! 12! 23! 6累加得到9所以输出9。这个例子看起来人畜无害一到n20左右就开始暴露出问题。很多新手第一次提交时根本不看数据范围写一个long long循环就交上去样例能过但一测大数据就挂。这种“样例过、提交挂”的体验几乎是每个学高精度的人都要经历的一道坎。为什么这题会被归到高精度计算章节因为阶乘的增长实在太快了。初中数学告诉我们n! 1 × 2 × 3 × … × n和指数函数相比阶乘的增长更猛。n只要到2020!已经是一个长达19位的数到5050!已经足足有65位到100100!的位数已经来到158位。更关键的是S 1! 2! … n! 里最大的那一项就是这么惊人的数字前面的项加起来在位数上几乎不会影响主导地位。1.2 从n20到n100中间隔着一个数据类型的鸿沟先看C里常见整数类型能表示的范围数据类型典型位数能表示的最大值int32位约21.47亿10位long long64位约9.22 × 10^1819位unsigned long long64位无符号约1.84 × 10^1920位20! 2,432,902,008,176,640,000这个数大约是2.43 × 10^18long long还能勉强放下。但21! 51,090,942,171,709,440,000约5.11 × 10^19已经超过unsigned long long的上限。也就是说如果你用long long算单个阶乘最多算到20!哪怕用unsigned long long单个阶乘也只能撑到20!到21!就彻底溢出。而这道题要求n可能到50甚至100从20到100之间隔着的不是“大了一点点”而是整整一百多个十进制位。这里有个特别容易让新手掉坑的地方阶乘的溢出不一定会立刻报错。C里的有符号整数溢出属于未定义行为在很多编译器上会“回绕”变成一个看似随机的大负数。比如你算到21!时long long可能变成一个负数再往后继续乘结果又负又正反复横跳。最后sum把一堆垃圾值加起来输出一个莫名其妙的数样例又能过这就非常折磨人。所以看到题目的数据范围是n≤100第一反应就应该是不能用普通整型做最终存储。2. 用long long硬算能撑到哪一步溢出观察实验2.1 最朴素的循环代码为了搞清楚“到底从哪个n开始崩”我建议你亲手做一次实验。写一个最简单的循环用long long保存阶乘和总和#include iostream using namespace std; int main() { int n; cin n; long long fact 1; long long sum 0; for (int i 1; i n; i) { fact * i; sum fact; } cout sum endl; return 0; }这段代码结构非常清爽fact从1开始每轮乘上i就得到了i!sum把当前阶乘累加上去。你输入10输出4037913完全正确输入20输出2561327494111820313看起来也很正常输入21就开始出现负值或乱跳的数字。有些编译器上21!已经溢出但sum还没立即崩溃等n更大一点fact彻底失控sum的结果就毫无意义。有同学会问“我能不能把fact和sum都改成unsigned long long”把有符号换成无符号只是把能表示的最大值翻了一倍21!还是放不下。就算你把数据类型换成__int128能到39!左右离100!依然差得远。所以这条路本质是死路方向不对。2.2 溢出后的表现和问题定位我自己当年调试的时候把中间结果一个个打印出来发现一个很明显的规律在n20之前fact打印出来的数值都是连续的、正常的n21开始fact突然变成一个负数n22以后fact在正负之间反复横跳。这时候再去检查sum就会发现sum的绝对值也变得毫无规律。这个现象的原因在于二进制补码表示中当一个数超过long long能表示的符号位范围后高位会被截断符号位被翻转。可以简单理解成一个“里程表”式溢出到了最大值后下一格回到最小值。但这只是最直观的理解严格来说有符号溢出的行为在C标准里是未定义编译器还可能做各种优化导致你看到的结果更不可预测。所以不要在未定义行为上纠结“为什么是负数”而是应该尽早意识到这个方案从一开始就不该用于大n。定位问题还有一种方法在循环里临时输出i和fact对照一张阶乘数值表。你会发现从某个i开始fact的值和数学上真实的i!完全不同。这就是普通整型方案的天花板。知道天花板在哪里才能下定决心换高精度。3. 高精度数组设计把数字拆开存就像用竖式手算3.1 数字在数组里的排布方式既然一个变量存不下大数那就用一组变量来存。这就是高精度算法的核心思想用一个数组表示一个超长的整数数组的每个位置存一个十进制位或者几位十进制位自己实现加、乘、进位等操作。最常见的做法是“小端存储”数组下标0存个位下标1存十位下标2存百位……这样低位在前、高位在后。为什么这么做因为做加法和乘法的时候都是从低位向高位逐位计算低位放在数组头部循环时从下标0开始自然推进进位也可以向后传播非常顺手。举个例子数字12345用数组表示就是a[0]5a[1]4a[2]3a[3]2a[4]1。输出的时候从数组尾部向头部倒着打印。很多新手第一次写高精度最容易搞反的是正序存导致进位时要在数组头部插入效率低且容易出错。所以建议一上来就养成低位在前的习惯。在阶乘和的场景里我们需要两个高精度数一个是fact保存当前已经算到的i!一个是sum保存累加结果。初始时fact为1代表1!也可以理解为0个数的乘积是1sum为0。3.2 实现乘法函数的细节阶乘的计算过程非常规律i! (i-1)! × i。也就是说我们可以把上一个阶乘的每一位都乘以i再处理进位就得到了新的阶乘。乘法函数可以这样写#include vector using namespace std; void multiply(vectorint a, int x) { int carry 0; for (size_t i 0; i a.size(); i) { int cur a[i] * x carry; a[i] cur % 10; carry cur / 10; } while (carry 0) { a.push_back(carry % 10); carry / 10; } }这段代码做的事情本质上和小学生列竖式做乘法一模一样用乘数x去乘被乘数的每一位每一位的结果加上来自低位的进位当前位保留个位十位以上的部分作为进位传给下一位。循环结束后如果进位还有剩余就把它逐位拆开追加到数组的高位。这里有个初学者容易踩的坑每次计算cur时用的是a[i]乘上x但是紧接着a[i]就被赋值为cur % 10。会不会影响下一位的运算不会。因为下一位用到的是a[i1]的原始值和已经被修改的a[i]无关。所以这个就地更新的写法是安全的。但如果你在循环里先修改了a[i]然后又拿修改后的a[i]去算进位就会出错。所以在代码里必须先用int cur保存“a[i] * x carry”这整个值再分别取出个位和进位顺序不能乱。3.3 实现累加函数的细节加法函数比乘法简单一些但同样要注意进位。我们要把当前阶乘fact加到sum上。由于两个数组长度可能不一样需要先补齐sum的长度至少和fact一样长。void addTo(vectorint sum, const vectorint a) { while (sum.size() a.size()) sum.push_back(0); int carry 0; for (size_t i 0; i a.size(); i) { int cur sum[i] a[i] carry; sum[i] cur % 10; carry cur / 10; } while (carry 0) { sum.push_back(carry % 10); carry / 10; } }这段代码的语义是sum sum a。循环里每一位执行sum[i] a[i] carry然后当前位存个位进位保留到下一位。循环结束后如果还有进位追加到sum高位。很多实现里会在循环里只看a.size()因为sum已经补齐到和a一样长所以没问题。但如果a比sum短而sum本来就有更高位那循环结束后更高位自然保留在sum里不需要额外处理。这也是低位在前的好处未知高位自动留在数组尾部。4. 赛场上容易忽略的进位顺序和累加逻辑4.1 乘法里的进位为什么不能顺手改值上一节给出的multiply函数是标准写法但如果你没理解它写错一个顺序结果就天差地别。我曾经看到有同学这样写for (int i 0; i a.size(); i) { a[i] a[i] * x; a[i 1] a[i] / 10; a[i] % 10; }这个写法的问题在于a[i 1]在还没被本轮以及后续处理时先被加上了来自低位的进位但a[i 1]自己后续还会被乘以x于是之前加进来的进位又被乘了一次x导致结果被放大很多倍。本质上是因为你把“进位加到下一位”和“下一位乘以x”两件事搞混了顺序。正确的原则是每一位先和x相乘然后再加上低位的进位得到完整结果后再拆位。也就是我在3.2节写的cur a[i] * x carry。carry是从低一位传上来的它不能再参与乘法只能被加到乘积结果上。想清楚这一点你就能理解为什么不能用一个临时数组去“边算边改相邻位”了。其实用临时数组也完全可以但循环会更繁琐直接在数组上更新只要保证每位计算一次顺序对了就OK。4.2 阶乘和是边算边加还是攒着统一加有的同学会先开一个二维vector把1!, 2!, …, n!全部算出来存在一个vectorvector 里最后再循环做加法。这样写逻辑上没问题但浪费空间也增加代码复杂度。因为阶乘的递推关系只需要知道当前阶乘和上一层阶乘之前算完的阶乘用完之后就再也不会用到。更优雅的做法是每一轮求出新的fact后立刻执行addTo(sum, fact)。这个“边算边加”的思路正好也是很多数学求和问题的通用模式。比如求1到n的和S 1 2 … n你可以用一个变量s每轮加i而不会把所有中间结果都存下来。高精度也是一样加法不会改变被加数fact所以fact可以继续用于下一轮乘法。这样整个程序只需要两个vector内存占用极小代码也更清爽。完整的核心循环是这样vectorint fact(1, 1); // fact 1当前是1! vectorint sum; // sum 0 for (int i 1; i n; i) { multiply(fact, i); // fact fact * i i! addTo(sum, fact); // sum fact }这里要特别说明初始i1时fact已经是1!乘以1之后还是1!加法再加一次1完全符合题目要求。如果你希望循环从2开始也可以先把1!手动加到sum但那样其实更容易出错。直接在循环里统一处理思路最简单。4.3 输出函数里的前导零陷阱高精度数字在数组里是低位在前输出时要从后往前打印。但这里有一个非常常见的错误直接用for循环倒序遍历vector会先输出最高位前面可能有的无效0。比如sum是0时数组里只有一个元素0倒序输出0没问题。但如果某个高精度数的有效位只有3位而数组长度因为之前的进位预留了很多0倒序输出就会变成“000123”。为了避免这种情况一定要从数组的最后一个有效位开始输出。最直接的写法是void print(const vectorint num) { int i (int)num.size() - 1; while (i 0 num[i] 0) --i; // 跳过前导0 for (; i 0; --i) { cout num[i]; } cout endl; }这个跳过前导0的逻辑在万进制下尤其重要。如果每个数组元素存的是4位十进制数输出时除了最高位其他位不足4位必须在前面补0但最高位一定不能补0。很多人在这一步被卡住AC代码因为输出格式错被反复判WA。5. 测试与边界从本地对拍到交卷前的一分钟5.1 特殊值n0、n1、n2很多在线评测题目会明确写n为正整数但作为严谨的开发者你还是应该处理一下n0这种边界情况。如果n01!到0!都没有阶乘和按常识应该是0。但如果题目的定义是空和为0那输出0即可。我的建议是在循环前如果n 0直接输出0并return这样只多两行代码能应对一些不规范的测试数据。n1时S1! 1输出1。n2时S1!2! 123。这些值都可以用普通整数心算验证。高精度代码处理这些极小数时也应该输出正确不应该因为进位逻辑而多出0或者少一位。顺便说一个我自己踩过的坑如果初始sum是一个空vector而n1循环一次后sum里会有一个元素1输出没问题但如果n0循环不执行sum还是空直接print空vector会越界。所以边界判断一定要放在print之前。你可以把sum初始化成长度为1、值为0的vector这样即使n0也能安全输出0。5.2 估算答案位数确认数组容量高精度实现里数组容量一般不需要预先指定因为vector可以动态生长。但如果你用固定数组比如int a[100000]就得先知道大概需要多少位。n100时答案是158位n1000时大概有2568位n10000时大概35660位。可以通过对数估算位数不需要真的算高精度。阶乘n!的位数可以用log10(n!) log10(1) log10(2) … log10(n)来计算而S大致等于n!这一项所以答案的位数也接近这个值。写一个小循环累加log10就能在本地快速估算double digits 0; for (int i 1; i n; i) digits log10((double)i); int len (int)digits 1; cout len endl;比如n100时digits约为157.97所以len是158。这个技巧特别适合检查自己高精度代码的空间是否足够也可以用来估算时间。如果你在数据范围很大的OJ上开固定数组建议用这个方法预留位数再加上一小段安全余量不要拍脑袋随便开10万位。5.3 用“小数据暴力大数据对数估算”验证完整的验证策略我建议分两步走。第一步用普通类型暴力跑小数据和高精度代码输出对比。比如n10输出应该是4037913n20输出应该是2561327494111820313。这些值都是可以用long long算出来的如果你高精度代码对不上说明加法或乘法有bug。第二步对大数据跑一个大致的位数检查。比如n50时答案应该是65位如果你的代码输出只有十几位那大概率是某些步骤被错误地截断成了int。n100时答案位数是158你可以用文本编辑器看一下输出文件的长度或者用程序检查一下位数是否一致。我当年刷题时本地写了一个Python脚本使用Python内置大整数算1!2!...n!然后和C高精度结果逐位比较。Python的大整数是现成的验算工具。虽然比赛时不一定允许用Python但本地对拍绝对是个好帮手。6. 常见变式取模、万进制、大数工具怎么选6.1 取模版本一行代码救命的思路实际比赛中阶乘和最常见的变式是求S mod M其中M通常是1000000007或类似的大质数。这种题不需要高精度只需要在每一步对取模结果进行运算即可。原理是模运算的分配率(a × b) mod M ((a mod M) × (b mod M)) mod M加法同理。实现起来非常简洁const long long MOD 1000000007LL; long long fact 1; long long sum 0; for (int i 1; i n; i) { fact fact * i % MOD; sum (sum fact) % MOD; } cout sum endl;这里需要特别注意fact和sum都要用long long或更大的类型因为在取模之前fact * i可能很大。如果M是1e97fact最大约为1e9乘上i最大可以是1e14左右依然在long long范围内所以安全。如果你用int乘法溢出可能会让你的答案在中间就出错。所以取模不是让你无脑用int而是让你用long long保证乘法不溢。很多人会问能不能先算出完整阶乘和再取模理论上可以但你计算完整阶乘和本身就是高精度问题既慢又费代码。比赛中看到取模马上切换到这个O(n)的长整型方案这是最合理的做法。6.2 万进制优化base从10改成10000当我们用数组每个位置存0~9一个100位的数需要100个数组元素。n10000时需要3万多元素乘法循环要执行3万多次其实也不算慢但进位处理比较繁琐。如果每个数组元素存0~9999同样存储量能表示的位数翻了4倍循环次数也大幅减少。这就是“万进制”高精度的思路。具体做法很简单把乘法、加法里所有的% 10和/ 10改成% 10000和/ 10000。但输出时要注意除最高位外的每一组都用四位格式输出不足四位前面补0const int BASE 10000; void multiply(vectorint a, int x) { int carry 0; for (size_t i 0; i a.size(); i) { int cur a[i] * x carry; a[i] cur % BASE; carry cur / BASE; } while (carry 0) { a.push_back(carry % BASE); carry / BASE; } } void addTo(vectorint sum, const vectorint a) { while (sum.size() a.size()) sum.push_back(0); int carry 0; for (size_t i 0; i a.size(); i) { int cur sum[i] a[i] carry; sum[i] cur % BASE; carry cur / BASE; } while (carry 0) { sum.push_back(carry % BASE); carry / BASE; } } void print(const vectorint a) { if (a.empty()) { cout 0 endl; return; } cout a.back(); for (int i (int)a.size() - 2; i 0; --i) { printf(%04d, a[i]); } cout endl; }这版代码在n10000时也能飞快运行。万进制是压位高精度的入门更极端的可以压到1e8甚至1e9但要小心int乘法溢出通常需要long long做中间值。我的建议是先掌握10进制的逻辑再改成万进制两者除了base不同其他几乎一样。6.3 要不要直接用Python/Java自带大数如果你想快速验证一道题Python的int可以无限大Java有BigInteger用它们写阶乘和几乎是天然的n int(input()) fact 1 total 0 for i in range(1, n 1): fact * i total fact print(total)这套代码简洁到让人怀疑人生。但竞赛中一旦数据范围到了n100000甚至更大Python的纯大数乘法可能变慢而且内存开销也更大。Java的BigInteger同样存在越算越慢的问题。C高精度的优势在于你可以控制进制、控制内存自己设计更高效的乘法比如FFT优化大整数乘法。如果只是为了快速拿下一道n100的题Python完全够用如果想在算法竞赛里长期混还是建议把C高精度练扎实。我个人在练习时会把三种方案都写一遍先Python暴力验证答案再C十进制高精度保证思路正确最后改成万进制压性能。这样一轮下来既理解了原理也能应对不同的数据范围。每次重刷这道1173阶乘和我都能看到当年的自己踩过的坑。如今再回看高精度没有多神秘本质就是把小时候学的竖式搬进数组再谨慎处理好进位和输出。希望这篇文章能帮你少走我走过的弯路。如果你在考试或练习中遇到阶乘相关的变式记住三个关键词先看数据范围再决定是普通循环、取模还是高精度高精度存储推荐低位在前输出前务必跳过前导0。把这三点刻进脑子里类似题目再变形也不容易翻车。