写大整数运算这件事我前后折腾过三轮第一轮是在纸上照着课本抄竖式代码写完了连 50 的阶乘都算不对第二轮是刷题时被卡在“高精度除以高精度”试商边界调了一整晚第三轮是真正需要处理万位级别的十进制数才发现自己一直用的十进制数组慢得离谱。所以这篇笔记不谈什么高深理论就是把大整数运算从存储结构、四则运算、压位优化到对拍验证这一整条链路捋清楚把我踩过的坑和算过的账摆出来。不管你是刚接触高精度、还在为进位写错而抓狂的新手还是已经能默写模板、但想搞清楚“为什么万进制比十进制快 16 倍”“Karatsuba 到底什么时候才值得上”的老手下面的内容应该都能对得上你的需求。大整数运算说白了就一句话当内置的 64 位整数装不下你要的数时自己用数组把十进制位管起来把加减乘除重新实现一遍。1. 先把边界摸清楚为什么内置类型不够用1.1 64 位整数的那条线画在哪里很多人对大整数的第一反应是“用 long long 不就行了”。这句话在 90% 的场景下是对的问题就出在剩下的 10%。有符号 64 位整数的上限是 922337203685477580719 位十进制数无符号 64 位是 1844674407370955161520 位。这两个数字值得背下来因为它决定了你什么时候必须换武器。阶乘是最经典的试金石。20! 等于 2432902008176640000还在 long long 里面21! 等于 51090942171709440000已经溢出。也就是说你写一个“求 n 的阶乘”的题目n 只要大于 20long long 就直接废了。斐波那契数列也一样第 92 项是 7540113804746346429第 93 项就顶破天花板。2 的幂更直观2^63 刚好卡在边界上2^64 就没了。这里有个很容易犯的错误觉得“我只要在中间过程用 long long 就不会溢出”。实际上大整数运算里最容易溢出的不是最终结果而是中间乘积。两个 9 位数相乘结果 18 位long long 装得下但如果你在循环里累加十次这样的乘积就接近 19 位了累加一百次直接爆掉。我在第一次写高精度乘法时就栽在这上面——单个乘积没问题累加器溢出输出的结果前面几位莫名其妙变成负数转换过来的垃圾值。注意判断要不要上大整数别看输入规模看中间结果的最大位数。乘法是位数相加累加是位数加 log这两条算一下心里就有数了。1.2 大整数运算真正出没的场景抛开“算法题”这个最直接的场景大整数其实在很多地方默默工作。组合数学里的卡特兰数、二项式系数稍微大一点的 n 就是几十位起步密码学里那些模幂运算底数和指数都是几百位上千位还有一些工程场景比如需要精确到分的财务汇总用浮点数会丢精度用定点整数又可能超出范围最后还是要落到大整数或者十进制字符串上。再有一种情况是“结果只需要输出不需要参与后续运算”。这种时候其实有更省事的做法——用支持任意精度整数的语言比如 Python 的 int 天生就是大整数Java 有 BigInteger直接把问题绕过去。但那属于“用工具解决问题”不是“理解问题”。如果你是在学算法、准备面试、或者需要在不支持大整数的环境里落地那还是得自己写。我个人的习惯是先用 Python 写一版暴力对拍程序再用 C 写正式实现两边结果比对这个流程后面会详细讲。还有一类场景容易被忽略进制转换。十进制字符串和二进制之间互转本质上就是大整数除以小整数、大整数乘小整数再加。你如果只处理 64 位以内的数用库函数就够了一旦要处理几百位的十进制数转二进制就必须自己写大整数。2. 存储结构怎么定从十进制数组到万进制压位2.1 低位在前是为了让进位不用搬家大整数的存储有一个几乎是约定俗成的选择把数字的每一位存进数组并且低位放在下标 0高位放在后面。新手第一次看到这个会觉得别扭因为人读数字是从高位读的。但你自己模拟一遍加法就明白了。假设你要算 999 1。如果高位在前数组是 [9,9,9]加完之后最后一位变 10要进位于是倒数第二位变 10再进位……进位是往“数组后面”传的。进位传到最前面时你还得在数组头部插入一个新元素——这个操作在 vector 里是 O(n) 的在整个数的最高位插入等于把整个数组往后挪一格。而如果低位在前数组是 [9,9,9]最低位是 a[0]进位是往 a[1]、a[2] 传位数不够时直接在尾部 push_back均摊 O(1)。减法同理借位是往高位借也就是往数组后面借。乘法的结果第 i 位和第 j 位的乘积落在第 ij 位这个下标相加的关系在低位在前的表示下最自然。所以低位在前不是为了炫技是为了让所有“向高位传播”的操作变成数组的尾部追加避免头部插入的开销。代价也有输出的时候要从后往前遍历比较大小的时候要先比长度再比高位这两个地方都得记得反过来处理。我第一次写比较函数时就忘了写成了从 a[0] 开始比结果 123 和 321 比出来是 123 大。2.2 进制选多大取决于中间结果会不会溢出最朴素的做法是每一位存一个 0 到 9 的数字也就是十进制。这个做法的好处是输出极其方便每一位直接打印不用补零坏处是慢因为数组长度等于十进制位数而乘法的复杂度是长度的平方。于是就有了“压位”每一位不存一个十进制数字而是存一个多位十进制块。常见的选择是存 4 位也就是万进制每个元素的范围是 0 到 9999。为什么是 4 位因为乘法的中间结果要装得下。两个小于 10000 的数相乘最大是 99980001加上进位也在 1 亿以内用 int 完全装得下如果取 5 位也就是十万进制两个元素相乘最大接近 1e10int 直接溢出必须全程用 long long反而变慢。如果用的是 64 位环境可以再往上取9 位也就是十亿进制两个元素相乘最大约 1e18刚好卡在 long long 上限附近必须用__int128或者把累加拆开。这条路在追求极致性能时值得走但调试成本会明显上升因为任何一个中间量溢出都表现为“结果大方向对、末尾几位错”极难定位。我用一张表把几种选择的权衡摆出来进制每元素位数单次乘积上界所需中间类型相对十进制提速十进制181int1x百进制29801int4x千进制3998001int9x万进制499980001int16x十亿进制9约 1e18long long / int12881x那个“相对提速”是怎么算出来的对于 O(n²) 的竖式乘法如果每个元素装 k 位十进制数组长度就变成原来的 1/k操作次数变成原来的 1/k²也就是速度快 k² 倍。万进制对应 4² 16 倍十亿进制对应 9² 81 倍。这是一个非常划算的买卖——代码结构的改动量很小收益却是数量级的。具体感受一下算一个 10 万位的十进制数乘法。用十进制存储长度 100000操作次数是 1e10这个量级在现代 CPU 上要跑几十秒到几分钟基本等于不可用。换成万进制长度变成 25000操作次数 6.25e8一秒以内能出结果。同一个算法只换了存储粒度从“不可用”变成“可用”。2.3 一个够用的结构体骨架我习惯把大整数封成一个结构体成员只有一个 vector 和一个符号位。符号位只在需要处理负数时加如果题目保证非负直接删掉能省不少心。struct Big { static const int BASE 10000; // 万进制 static const int W 4; // 每个元素承载 4 位十进制 vectorint a; // a[0] 最低位, a.back() 最高位 Big(long long x 0) { if (x 0) { a.push_back(0); return; } while (x 0) { a.push_back((int)(x % BASE)); x / BASE; } } void trim() { // 去掉高位多余的 0 while (a.size() 1 a.back() 0) a.pop_back(); } };构造函数接收 long long 而不是 int是因为经常需要从 64 位常量直接构造比如初始化一个Big(1000000007LL)。如果只写 int 版本编译器会做隐式转换但遇到超过 int 范围的常量就悄悄截断了这种 bug 找起来很折磨。trim()这个函数看着不起眼但它是后面所有运算的安全阀。减法的结果可能出现高位全零乘法的结果尾部预留了空间如果不 trim长度比较就会出错进而导致所有基于长度的比较逻辑全盘失效。我的建议是每个返回 Big 的函数在 return 之前都无条件调一次 trim别省这一行。3. 加减乘除逐位拆解3.1 加法进位是一个“延迟结算”加法的核心是进位。你从最低位开始逐位相加当前位的和超过进制基数就把多出来的部分留给下一位。这个过程用代码写出来非常短Big add(const Big x, const Big y) { Big z; size_t n max(x.a.size(), y.a.size()) 1; // 预留一位给最高进位 z.a.assign(n, 0); int carry 0; for (size_t i 0; i n; i) { int s carry; if (i x.a.size()) s x.a[i]; if (i y.a.size()) s y.a[i]; z.a[i] s % Big::BASE; carry s / Big::BASE; } z.trim(); return z; }这里有两个细节值得说。第一是数组长度取max 1多出来的那一位专门留给最高位产生的进位。比如 9999 1万进制下是 [9999] [1]结果是 [0, 1]需要两个元素如果只开 max 长度写越界。多开一位的成本可以忽略但省下来的是段错误和玄学结果。第二是s % BASE和s / BASE这一对操作。编译器对常量取模和除法会有优化但如果 BASE 是运行时变量这两条就是真正的除法指令在热循环里很贵。所以我一直把 BASE 写成static const让编译器能把它当编译期常量处理。如果你追求极致可以把 BASE 设成 2 的幂用位运算替代但那样输出就得自己做进制转换取舍看场景。提示加法里最常见的错误不是进位算错而是忘了处理两个数长度不同的情况。一定要在循环里判断i x.a.size()不能默认两个数组一样长。3.2 减法先比大小再谈借位减法比加法麻烦因为它有前提条件被减数要不小于减数。如果题目可能出现小数减大数你得先比较大小如果反了就交换位置、算出结果、再补一个负号。比较函数的写法要特别注意因为低位在前int cmp(const Big x, const Big y) { if (x.a.size() ! y.a.size()) return x.a.size() y.a.size() ? -1 : 1; for (int i (int)x.a.size() - 1; i 0; --i) if (x.a[i] ! y.a[i]) return x.a[i] y.a[i] ? -1 : 1; return 0; }先比长度长度相同再从高位往低位比。这两步顺序不能反因为长度不同时从高位比可能刚好撞上高位都是 0 的情况比出来的结论是错的。比如 10000 和 999万进制下分别是 [0,1] 和 [999]如果直接比 a[1]1 0结论正确纯属巧合换成 10000 和 9999[0,1] 和 [9999]a[1] 是 1 0结论也对。但换成 万进制下的 100000000[0,0,1]和 99999999[9999,9999]长度 3 2正确如果从高位比a[2]1 对 a[2] 不存在……总之不用纠结先比长度是唯一稳妥的写法。减法本体Big sub(const Big x, const Big y) { // 前置条件: x y Big z; z.a.assign(x.a.size(), 0); int borrow 0; for (size_t i 0; i x.a.size(); i) { int s x.a[i] - borrow - (i y.a.size() ? y.a[i] : 0); if (s 0) { s Big::BASE; borrow 1; } else borrow 0; z.a[i] s; } z.trim(); return z; }借位的写法有两种风格一种是先减再判断负数补基数、置借位另一种是先加上基数再取模。第一种更直观我倾向于它因为调试时能直接在脑子里对上“这一位不够减向高位借一当 BASE”。这里有个隐藏的坑循环走完之后 borrow 应该是 0。如果借位没消掉说明 x y前置条件被破坏了结果是错的。稳妥的做法是在循环末尾加一句断言或者在有符号版本里靠符号位处理。3.3 乘法竖式的本质是卷积先看高精度乘低精度这是最常用的一种。很多题目只需要乘一个 int 范围内的数比如算阶乘、算 2 的幂这种场景下不需要写完整的高精度乘法Big mulSmall(const Big x, int k) { // 要求 0 k BASE Big z; z.a.assign(x.a.size() 1, 0); long long carry 0; for (size_t i 0; i x.a.size(); i) { long long cur (long long)x.a[i] * k carry; z.a[i] (int)(cur % Big::BASE); carry cur / Big::BASE; } z.a[x.a.size()] (int)carry; z.trim(); return z; }注意cur用的是 long long。虽然前面算过 a[i] * k 最大不超过 1e8int 装得下但再加一个 carry 就有溢出风险尤其是 k 接近 BASE 的时候。这类“理论上不溢出、实际差一点点”的地方用 long long 兜底是最省心的。高精度乘高精度就是双重循环Big mul(const Big x, const Big y) { Big z; z.a.assign(x.a.size() y.a.size(), 0); for (size_t i 0; i x.a.size(); i) { long long carry 0; for (size_t j 0; j y.a.size() || carry; j) { long long cur z.a[i j] carry (j y.a.size() ? (long long)x.a[i] * y.a[j] : 0); z.a[i j] (int)(cur % Big::BASE); carry cur / Big::BASE; } } z.trim(); return z; }这段的写法有点讲究内层循环的条件是j y.a.size() || carry也就是“还有乘数要处理”或者“还有进位没消化”。这样写的好处是不用单独处理进位传播进位会在 j 走到 y 末尾之后继续沿着 z 往后推。很多人的写法是内层只循环到 y 的末尾然后把 carry 强行塞进 z.a[i y.size()]如果那个位置本来就有值加法会丢失——这个 bug 只在特定数据下出现非常难复现。从数学角度看竖式乘法本质上是多项式卷积结果的第 k 位等于所有 i j k 的 a[i] * b[j] 之和。理解这一点之后你就能明白为什么复杂度是 O(n²)——每个 i 都要和每个 j 配对一次。也正因为它是卷积才有后面快速傅里叶变换那一套优化不过那是另一个量级的话题了。3.4 除法高精度除高精度的试商写法除法是大整数四则里最难的没有之一。高精度除以低精度还好本质上是“从高位到低位逐位试除”每一步都是 long long 级别的小学除法Big divSmall(const Big x, int k, int rem) { // k 0 Big z; z.a.assign(x.a.size(), 0); long long r 0; for (int i (int)x.a.size() - 1; i 0; --i) { long long cur r * Big::BASE x.a[i]; z.a[i] (int)(cur / k); r cur % k; } rem (int)r; z.trim(); return z; }注意这里是从高位往低位遍历因为除法的方向和人手算一致必须从最高位开始才能确定商的每一位。这和加减乘都是反的写的时候容易顺手写成从 0 开始结果是完全错的。高精度除以高精度就得用长除法维护一个余数每次把被除数的下一位“落”下来然后用 0 到 BASE-1 去试商。试商的方式有两种线性扫描和二分。线性扫描最坏要试 BASE 次BASE 是 10000 的话就是一万次乘上数组长度明显偏慢二分是 log(BASE) 次也就是 14 次左右实际用起来快得多Big div(const Big x, const Big y, Big rem) { Big q; q.a.assign(x.a.size(), 0); rem Big(0); for (int i (int)x.a.size() - 1; i 0; --i) { rem.a.insert(rem.a.begin(), x.a[i]); // 落下一位 rem.trim(); int lo 0, hi Big::BASE - 1, best 0; while (lo hi) { int mid (lo hi) 1; if (cmp(mulSmall(y, mid), rem) 0) { best mid; lo mid 1; } else hi mid - 1; } q.a[i] best; rem sub(rem, mulSmall(y, best)); } q.trim(); return q; }二分试商能成立的前提是y * mid关于 mid 单调递增。这个显然成立因为 y 是非负的。但要注意 mid 的范围是[0, BASE-1]如果 y 很小、余数很大商可能会超过 BASE-1——不会因为在长除法里每次落一位之后余数一定小于 y * BASE所以商一定小于 BASE。rem.a.insert(rem.a.begin(), x.a[i])这一句是 O(n) 的插入看起来低效但对正确性没影响。如果你的数据规模很大可以改成给 rem 预留长度、用下标写入的方式能省掉内存搬移。我在实际代码里就是把 rem 当成定长数组管理的不过为了笔记可读性这里保留了直观写法。4. 性能这条线压位、Karatsuba 与阈值实测4.1 竖式乘法到底慢在哪里竖式乘法的时间全部花在内层循环那一次乘加。对于 n 个元素的数组内层循环执行 n² 次每次包含一次乘法、一次加法、一次取模、一次除法。取模和除法的开销大致是乘法的几倍所以整体常数不小。对工程实践来说真正关心的不是 n² 这个渐进式而是“多少位以内能在可接受时间内算完”。我在手头那台开发机上做过一组粗糙的测量用万进制竖式乘代码就是上面那段没有做任何特殊优化十进制位数数组长度万进制内层循环次数实测耗时1 千2506.3 万小于 1 毫秒1 万2500625 万约 6 毫秒5 万125001.56 亿约 350 毫秒10 万250006.25 亿约 1.5 秒50 万12500015.6 亿一分钟以上这组数据不是精确基准机器状态、编译选项、缓存命中都会影响但量级关系是可靠的。可以看出1 万位以内竖式完全够用10 万位开始变得难受50 万位基本没法接受。这就是为什么在真正需要处理超长数字的场景里人们会去研究更快的乘法。还有一个容易被忽略的因素内存访问。内层循环里z.a[i j]是顺序访问x.a[i]在外层固定y.a[j]顺序访问缓存友好度其实不错。但z数组会反复被读改写如果数组长度超过 L3 缓存每次读写都要走内存性能会断崖式下降。我在 50 万位那组数据上就观察到了这个现象——按循环次数算理论上应该只比 10 万位慢 25 倍实际慢了 40 倍以上。4.2 压位能带来多少提升前面算过万进制相对十进制提速 16 倍。这个数字我实测验过同一段竖式乘法逻辑一份用十进制数组一份用万进制数组算 1 万位的数十进制那份要 90 毫秒左右万进制 6 毫秒左右比例接近 16和理论吻合。为什么压位这么划算因为它是“免费的午餐”——算法结构完全不变只是把存储粒度从 1 位改成 k 位操作次数就降了 k² 倍。代码改动量极小主要是三处常量 BASE 从 10 改成 10000输出时除了最高位其余每节都要补零到 4 位输入时从字符串末尾往前每 4 个字符切一段。输出补零是压位最容易出 bug 的地方。假设结果是 [1, 23]也就是 23 * 10000 1 230001。如果你直接打印 1 和 23得到的是 123错了。正确做法是最高位正常打印其余位用%04d格式化void print(const Big x) { printf(%d, x.a.back()); // 最高位不补零 for (int i (int)x.a.size() - 2; i 0; --i) printf(%04d, x.a[i]); // 其余位补到 4 位 }这个 bug 我见过太多次了尤其是结果中间刚好有若干个零的时候比如 100000001万进制下是 [1, 0, 1]输出成 101 还是 100000001 全看有没有补零。注意从字符串输入大整数时也要按 4 位一组从后往前切分最后剩下的不足 4 位单独处理。不能从头往前切否则高位会错位。4.3 Karatsuba 什么时候才真正划算Karatsuba 算法是分治乘法的入门款思路是把一个 n 位的数拆成高低两半用三次规模减半的乘法拼出结果而不是四次。递推式是 T(n) 3T(n/2) O(n)解出来是 O(n^1.585)。指数从 2 降到 1.585听起来很美。但实际写起来你会发现教科书不会告诉你的一件事是Karatsuba 在 n 很小的时候比竖式还慢。原因有三递归调用有开销拆分数、合并结果需要额外的加法和数组分配三个子问题虽然规模减半但内存分配次数翻了好几倍。所以真正的实现都会设一个阈值n 小于阈值时直接切回竖式。这个阈值是多少我试过几个值用万进制数组、算 10 万位乘 10 万位粗略结果如下阈值数组长度10 万位耗时16约 1.1 秒32约 0.8 秒64约 0.65 秒128约 0.72 秒256约 0.95 秒不切纯竖式约 1.5 秒可以看到阈值在 64 附近是个比较甜的点相对纯竖式大约 2.3 倍加速。这个数字远没有 n^0.415 的理论比值那么夸张因为在 10 万位这个规模上log 因子的影响还很有限而且内存分配的开销吃掉了一部分收益。我换成预分配好缓冲区的写法之后才勉强做到 2.5 倍左右。所以我的建议很明确如果你的数据规模在 1 万位以内别碰 Karatsuba竖式加万进制足够了规模在 10 万位量级可以上 Karatsuba但要记得设阈值、预分配规模到百万位那就该考虑 NTT 那一套了Karatsuba 也救不了你。5. 高频踩坑与排查清单5.1 清零、进位、前导零三件套大整数运算的 bug 有 80% 集中在这三件事上我按出现频率排个序。第一位是结果没清零。乘法的 z 数组如果只resize不初始化里面是随机值后面累加的时候随机值和真实结果混在一起输出的数字会既像对的又像错的。用assign(n, 0)而不是resize(n)能一次性解决。我现在的习惯是所有构造 Big 的地方都用assign。第二位是进位没消化完。加法里数组多开一位就是为这个乘法里内层循环条件写|| carry也是为这个除法里余数最后要单独返回。这三处的处理方式不同但本质都是“进位/余数不会自动消失必须显式处理”。第三位是前导零。大整数的长度是所有逻辑的基础如果结果存在高位零长度就虚胖了。后果很隐蔽比较大小会错、输出会多打印一堆零、后续运算会变慢但结果可能还是对的——最后这条最要命因为测试用例可能刚好覆盖不到。void trim() { while (a.size() 1 a.back() 0) a.pop_back(); }注意条件里的a.size() 1不能写成!a.empty()。因为数值 0 的合法表示就是[0]如果把长度削到 0后面所有访问a.back()的地方都会崩。5.2 输出与前导零除了压位的补零还有一个常见问题是“零值输出”。如果结果就是 0而你在减法里用 trim 把长度削到了一个元素输出 0这是对的但如果某个中间结果被削成了空数组输出就是空字符串评测机会判格式错误但不会告诉你为什么。另一个问题是负数的输出。如果你实现了符号位输出时要先判断符号再打印绝对值且要特别注意“负零”的情况两个相等的数相减结果是 0如果符号位逻辑写错会输出 -0。我的做法是在减法里统一处理——如果cmp(x, y) 0直接返回 Big(0)符号位置 false。5.3 边界与内存几个必须单独测的边界0 加 0、0 减 0、0 乘任何数、被除数为 0、除数为 1、两个数相等、位数差一位比如 1000 和 999。位数差一位是最容易出问题的因为进位链会跨过整个数组。999 1、1000 - 1、9999 1 这三个用例我建议写进每次的回归测试里它们能覆盖数组扩容、进位连锁、借位连锁三种情况。内存方面大整数运算是典型的“小数据看不出问题、大数据直接崩”的类型。乘法要开x.size() y.size()的空间除法里每次试商都会产生临时 Big递归里会叠加。如果你在循环里反复做大整数乘法比如算 10 万位的阶乘那临时对象的分配次数是百万级的光内存分配就能把你拖死。解决办法是预先分配好缓冲区把临时结果传引用进去。6. 一套可以直接抄的实战流程6.1 模板准备顺序我现在的习惯是按这个顺序写先写结构体和构造函数再写 trim 和 cmp然后写加减最后写乘除。这个顺序不是随便定的因为 cmp 是减法、除法、比较的基础没有它后面全是错的加减是乘除的子过程Karatsuba 里全靠加减先把加减测通乘法出错时你才能确定问题在乘法本身。写完一个函数就立刻测一个别攒着一起测。大整数运算的错误会互相掩盖乘法错了你用除法去验证除法的结果也不对你根本不知道是哪个错了。6.2 用阶乘和 2 的幂做回归测试阶乘是最好的测试用例因为它同时覆盖乘法、进位、长度增长。2 的幂也好用因为它的十进制表示有规律你可以直接肉眼检查。Big fact(int n) { Big r(1); for (int i 2; i n; i) r mulSmall(r, i); return r; }100! 是 158 位200! 是 375 位1000! 是 2568 位。这三个规模分别对应“小、中、大”跑一遍看输出长度对不对能快速筛掉明显的 bug。如果长度对但值不对基本就是进位或者进位链的问题。6.3 与 Python 大整数对拍这是我最推荐的一步也是很多人懒得做的一步。Python 的 int 是天生的任意精度整数你拿它当标准答案把自己的 C 实现跑一遍随机数据两边一比就知道对不对。import random, subprocess for _ in range(200): a random.randint(0, 10**500) b random.randint(1, 10**300) # 把你的程序输出和 a * b 比一比具体做法是把 C 程序改成从标准输入读两个大整数字符串输出运算结果然后 Python 生成随机数据、调用子进程、比对。500 位以内的数Python 算起来是瞬间的事200 组数据几秒钟就跑完了。对拍的价值在于它能覆盖你根本想不到的边界。我曾经写过一个减法所有手写用例都过对拍跑到第 37 组才崩——那组数据是 10000 减 9999万进制下高位刚好产生了一串零trim 之后长度变成 1后面某个地方访问了a[1]。这种用例靠人想是想不出来的。6.4 一个检查清单最后把我自己在提交前会过一遍的检查项列出来都是被坑出来的乘法结果数组初始化用assign(n, 0)不是resize(n)加法数组长度取max 1减法的前置条件x y是否保证不保证时符号是否处理trim 的条件是size() 1输出最高位不补零其余位补到 W 位压位输入时从字符串末尾往前按 W 切除法里 mid 的上界是BASE - 10 的各种运算单独测一遍这套流程走下来我不敢说能写出零 bug 的实现但至少能在提交前把 90% 的低级错误挡掉。剩下那 10%交给对拍。我个人在实际操作中的体会是大整数运算真正的难点不在算法本身而在“状态管理”——进位、借位、长度、符号这四个状态贯穿所有运算任何一个在某个分支里忘了更新就会变成只在特定数据下出现的幽灵 bug。所以与其追求写法上的精巧不如把每个函数都写成“先算干净、再 trim、再返回”的固定套路让每个分支的状态都收敛到同一个地方。压位和 Karatsuba 那些优化等你把基础版本对拍跑通了再去动否则你连是优化写错了还是原逻辑错了都分不清。
写大整数运算这件事我前后折腾过三轮第一轮是在纸上照着课本抄竖式代码写完了连 50 的阶乘都算不对第二轮是刷题时被卡在“高精度除以高精度”试商边界调了一整晚第三轮是真正需要处理万位级别的十进制数才发现自己一直用的十进制数组慢得离谱。所以这篇笔记不谈什么高深理论就是把大整数运算从存储结构、四则运算、压位优化到对拍验证这一整条链路捋清楚把我踩过的坑和算过的账摆出来。不管你是刚接触高精度、还在为进位写错而抓狂的新手还是已经能默写模板、但想搞清楚“为什么万进制比十进制快 16 倍”“Karatsuba 到底什么时候才值得上”的老手下面的内容应该都能对得上你的需求。大整数运算说白了就一句话当内置的 64 位整数装不下你要的数时自己用数组把十进制位管起来把加减乘除重新实现一遍。1. 先把边界摸清楚为什么内置类型不够用1.1 64 位整数的那条线画在哪里很多人对大整数的第一反应是“用 long long 不就行了”。这句话在 90% 的场景下是对的问题就出在剩下的 10%。有符号 64 位整数的上限是 922337203685477580719 位十进制数无符号 64 位是 1844674407370955161520 位。这两个数字值得背下来因为它决定了你什么时候必须换武器。阶乘是最经典的试金石。20! 等于 2432902008176640000还在 long long 里面21! 等于 51090942171709440000已经溢出。也就是说你写一个“求 n 的阶乘”的题目n 只要大于 20long long 就直接废了。斐波那契数列也一样第 92 项是 7540113804746346429第 93 项就顶破天花板。2 的幂更直观2^63 刚好卡在边界上2^64 就没了。这里有个很容易犯的错误觉得“我只要在中间过程用 long long 就不会溢出”。实际上大整数运算里最容易溢出的不是最终结果而是中间乘积。两个 9 位数相乘结果 18 位long long 装得下但如果你在循环里累加十次这样的乘积就接近 19 位了累加一百次直接爆掉。我在第一次写高精度乘法时就栽在这上面——单个乘积没问题累加器溢出输出的结果前面几位莫名其妙变成负数转换过来的垃圾值。注意判断要不要上大整数别看输入规模看中间结果的最大位数。乘法是位数相加累加是位数加 log这两条算一下心里就有数了。1.2 大整数运算真正出没的场景抛开“算法题”这个最直接的场景大整数其实在很多地方默默工作。组合数学里的卡特兰数、二项式系数稍微大一点的 n 就是几十位起步密码学里那些模幂运算底数和指数都是几百位上千位还有一些工程场景比如需要精确到分的财务汇总用浮点数会丢精度用定点整数又可能超出范围最后还是要落到大整数或者十进制字符串上。再有一种情况是“结果只需要输出不需要参与后续运算”。这种时候其实有更省事的做法——用支持任意精度整数的语言比如 Python 的 int 天生就是大整数Java 有 BigInteger直接把问题绕过去。但那属于“用工具解决问题”不是“理解问题”。如果你是在学算法、准备面试、或者需要在不支持大整数的环境里落地那还是得自己写。我个人的习惯是先用 Python 写一版暴力对拍程序再用 C 写正式实现两边结果比对这个流程后面会详细讲。还有一类场景容易被忽略进制转换。十进制字符串和二进制之间互转本质上就是大整数除以小整数、大整数乘小整数再加。你如果只处理 64 位以内的数用库函数就够了一旦要处理几百位的十进制数转二进制就必须自己写大整数。2. 存储结构怎么定从十进制数组到万进制压位2.1 低位在前是为了让进位不用搬家大整数的存储有一个几乎是约定俗成的选择把数字的每一位存进数组并且低位放在下标 0高位放在后面。新手第一次看到这个会觉得别扭因为人读数字是从高位读的。但你自己模拟一遍加法就明白了。假设你要算 999 1。如果高位在前数组是 [9,9,9]加完之后最后一位变 10要进位于是倒数第二位变 10再进位……进位是往“数组后面”传的。进位传到最前面时你还得在数组头部插入一个新元素——这个操作在 vector 里是 O(n) 的在整个数的最高位插入等于把整个数组往后挪一格。而如果低位在前数组是 [9,9,9]最低位是 a[0]进位是往 a[1]、a[2] 传位数不够时直接在尾部 push_back均摊 O(1)。减法同理借位是往高位借也就是往数组后面借。乘法的结果第 i 位和第 j 位的乘积落在第 ij 位这个下标相加的关系在低位在前的表示下最自然。所以低位在前不是为了炫技是为了让所有“向高位传播”的操作变成数组的尾部追加避免头部插入的开销。代价也有输出的时候要从后往前遍历比较大小的时候要先比长度再比高位这两个地方都得记得反过来处理。我第一次写比较函数时就忘了写成了从 a[0] 开始比结果 123 和 321 比出来是 123 大。2.2 进制选多大取决于中间结果会不会溢出最朴素的做法是每一位存一个 0 到 9 的数字也就是十进制。这个做法的好处是输出极其方便每一位直接打印不用补零坏处是慢因为数组长度等于十进制位数而乘法的复杂度是长度的平方。于是就有了“压位”每一位不存一个十进制数字而是存一个多位十进制块。常见的选择是存 4 位也就是万进制每个元素的范围是 0 到 9999。为什么是 4 位因为乘法的中间结果要装得下。两个小于 10000 的数相乘最大是 99980001加上进位也在 1 亿以内用 int 完全装得下如果取 5 位也就是十万进制两个元素相乘最大接近 1e10int 直接溢出必须全程用 long long反而变慢。如果用的是 64 位环境可以再往上取9 位也就是十亿进制两个元素相乘最大约 1e18刚好卡在 long long 上限附近必须用__int128或者把累加拆开。这条路在追求极致性能时值得走但调试成本会明显上升因为任何一个中间量溢出都表现为“结果大方向对、末尾几位错”极难定位。我用一张表把几种选择的权衡摆出来进制每元素位数单次乘积上界所需中间类型相对十进制提速十进制181int1x百进制29801int4x千进制3998001int9x万进制499980001int16x十亿进制9约 1e18long long / int12881x那个“相对提速”是怎么算出来的对于 O(n²) 的竖式乘法如果每个元素装 k 位十进制数组长度就变成原来的 1/k操作次数变成原来的 1/k²也就是速度快 k² 倍。万进制对应 4² 16 倍十亿进制对应 9² 81 倍。这是一个非常划算的买卖——代码结构的改动量很小收益却是数量级的。具体感受一下算一个 10 万位的十进制数乘法。用十进制存储长度 100000操作次数是 1e10这个量级在现代 CPU 上要跑几十秒到几分钟基本等于不可用。换成万进制长度变成 25000操作次数 6.25e8一秒以内能出结果。同一个算法只换了存储粒度从“不可用”变成“可用”。2.3 一个够用的结构体骨架我习惯把大整数封成一个结构体成员只有一个 vector 和一个符号位。符号位只在需要处理负数时加如果题目保证非负直接删掉能省不少心。struct Big { static const int BASE 10000; // 万进制 static const int W 4; // 每个元素承载 4 位十进制 vectorint a; // a[0] 最低位, a.back() 最高位 Big(long long x 0) { if (x 0) { a.push_back(0); return; } while (x 0) { a.push_back((int)(x % BASE)); x / BASE; } } void trim() { // 去掉高位多余的 0 while (a.size() 1 a.back() 0) a.pop_back(); } };构造函数接收 long long 而不是 int是因为经常需要从 64 位常量直接构造比如初始化一个Big(1000000007LL)。如果只写 int 版本编译器会做隐式转换但遇到超过 int 范围的常量就悄悄截断了这种 bug 找起来很折磨。trim()这个函数看着不起眼但它是后面所有运算的安全阀。减法的结果可能出现高位全零乘法的结果尾部预留了空间如果不 trim长度比较就会出错进而导致所有基于长度的比较逻辑全盘失效。我的建议是每个返回 Big 的函数在 return 之前都无条件调一次 trim别省这一行。3. 加减乘除逐位拆解3.1 加法进位是一个“延迟结算”加法的核心是进位。你从最低位开始逐位相加当前位的和超过进制基数就把多出来的部分留给下一位。这个过程用代码写出来非常短Big add(const Big x, const Big y) { Big z; size_t n max(x.a.size(), y.a.size()) 1; // 预留一位给最高进位 z.a.assign(n, 0); int carry 0; for (size_t i 0; i n; i) { int s carry; if (i x.a.size()) s x.a[i]; if (i y.a.size()) s y.a[i]; z.a[i] s % Big::BASE; carry s / Big::BASE; } z.trim(); return z; }这里有两个细节值得说。第一是数组长度取max 1多出来的那一位专门留给最高位产生的进位。比如 9999 1万进制下是 [9999] [1]结果是 [0, 1]需要两个元素如果只开 max 长度写越界。多开一位的成本可以忽略但省下来的是段错误和玄学结果。第二是s % BASE和s / BASE这一对操作。编译器对常量取模和除法会有优化但如果 BASE 是运行时变量这两条就是真正的除法指令在热循环里很贵。所以我一直把 BASE 写成static const让编译器能把它当编译期常量处理。如果你追求极致可以把 BASE 设成 2 的幂用位运算替代但那样输出就得自己做进制转换取舍看场景。提示加法里最常见的错误不是进位算错而是忘了处理两个数长度不同的情况。一定要在循环里判断i x.a.size()不能默认两个数组一样长。3.2 减法先比大小再谈借位减法比加法麻烦因为它有前提条件被减数要不小于减数。如果题目可能出现小数减大数你得先比较大小如果反了就交换位置、算出结果、再补一个负号。比较函数的写法要特别注意因为低位在前int cmp(const Big x, const Big y) { if (x.a.size() ! y.a.size()) return x.a.size() y.a.size() ? -1 : 1; for (int i (int)x.a.size() - 1; i 0; --i) if (x.a[i] ! y.a[i]) return x.a[i] y.a[i] ? -1 : 1; return 0; }先比长度长度相同再从高位往低位比。这两步顺序不能反因为长度不同时从高位比可能刚好撞上高位都是 0 的情况比出来的结论是错的。比如 10000 和 999万进制下分别是 [0,1] 和 [999]如果直接比 a[1]1 0结论正确纯属巧合换成 10000 和 9999[0,1] 和 [9999]a[1] 是 1 0结论也对。但换成 万进制下的 100000000[0,0,1]和 99999999[9999,9999]长度 3 2正确如果从高位比a[2]1 对 a[2] 不存在……总之不用纠结先比长度是唯一稳妥的写法。减法本体Big sub(const Big x, const Big y) { // 前置条件: x y Big z; z.a.assign(x.a.size(), 0); int borrow 0; for (size_t i 0; i x.a.size(); i) { int s x.a[i] - borrow - (i y.a.size() ? y.a[i] : 0); if (s 0) { s Big::BASE; borrow 1; } else borrow 0; z.a[i] s; } z.trim(); return z; }借位的写法有两种风格一种是先减再判断负数补基数、置借位另一种是先加上基数再取模。第一种更直观我倾向于它因为调试时能直接在脑子里对上“这一位不够减向高位借一当 BASE”。这里有个隐藏的坑循环走完之后 borrow 应该是 0。如果借位没消掉说明 x y前置条件被破坏了结果是错的。稳妥的做法是在循环末尾加一句断言或者在有符号版本里靠符号位处理。3.3 乘法竖式的本质是卷积先看高精度乘低精度这是最常用的一种。很多题目只需要乘一个 int 范围内的数比如算阶乘、算 2 的幂这种场景下不需要写完整的高精度乘法Big mulSmall(const Big x, int k) { // 要求 0 k BASE Big z; z.a.assign(x.a.size() 1, 0); long long carry 0; for (size_t i 0; i x.a.size(); i) { long long cur (long long)x.a[i] * k carry; z.a[i] (int)(cur % Big::BASE); carry cur / Big::BASE; } z.a[x.a.size()] (int)carry; z.trim(); return z; }注意cur用的是 long long。虽然前面算过 a[i] * k 最大不超过 1e8int 装得下但再加一个 carry 就有溢出风险尤其是 k 接近 BASE 的时候。这类“理论上不溢出、实际差一点点”的地方用 long long 兜底是最省心的。高精度乘高精度就是双重循环Big mul(const Big x, const Big y) { Big z; z.a.assign(x.a.size() y.a.size(), 0); for (size_t i 0; i x.a.size(); i) { long long carry 0; for (size_t j 0; j y.a.size() || carry; j) { long long cur z.a[i j] carry (j y.a.size() ? (long long)x.a[i] * y.a[j] : 0); z.a[i j] (int)(cur % Big::BASE); carry cur / Big::BASE; } } z.trim(); return z; }这段的写法有点讲究内层循环的条件是j y.a.size() || carry也就是“还有乘数要处理”或者“还有进位没消化”。这样写的好处是不用单独处理进位传播进位会在 j 走到 y 末尾之后继续沿着 z 往后推。很多人的写法是内层只循环到 y 的末尾然后把 carry 强行塞进 z.a[i y.size()]如果那个位置本来就有值加法会丢失——这个 bug 只在特定数据下出现非常难复现。从数学角度看竖式乘法本质上是多项式卷积结果的第 k 位等于所有 i j k 的 a[i] * b[j] 之和。理解这一点之后你就能明白为什么复杂度是 O(n²)——每个 i 都要和每个 j 配对一次。也正因为它是卷积才有后面快速傅里叶变换那一套优化不过那是另一个量级的话题了。3.4 除法高精度除高精度的试商写法除法是大整数四则里最难的没有之一。高精度除以低精度还好本质上是“从高位到低位逐位试除”每一步都是 long long 级别的小学除法Big divSmall(const Big x, int k, int rem) { // k 0 Big z; z.a.assign(x.a.size(), 0); long long r 0; for (int i (int)x.a.size() - 1; i 0; --i) { long long cur r * Big::BASE x.a[i]; z.a[i] (int)(cur / k); r cur % k; } rem (int)r; z.trim(); return z; }注意这里是从高位往低位遍历因为除法的方向和人手算一致必须从最高位开始才能确定商的每一位。这和加减乘都是反的写的时候容易顺手写成从 0 开始结果是完全错的。高精度除以高精度就得用长除法维护一个余数每次把被除数的下一位“落”下来然后用 0 到 BASE-1 去试商。试商的方式有两种线性扫描和二分。线性扫描最坏要试 BASE 次BASE 是 10000 的话就是一万次乘上数组长度明显偏慢二分是 log(BASE) 次也就是 14 次左右实际用起来快得多Big div(const Big x, const Big y, Big rem) { Big q; q.a.assign(x.a.size(), 0); rem Big(0); for (int i (int)x.a.size() - 1; i 0; --i) { rem.a.insert(rem.a.begin(), x.a[i]); // 落下一位 rem.trim(); int lo 0, hi Big::BASE - 1, best 0; while (lo hi) { int mid (lo hi) 1; if (cmp(mulSmall(y, mid), rem) 0) { best mid; lo mid 1; } else hi mid - 1; } q.a[i] best; rem sub(rem, mulSmall(y, best)); } q.trim(); return q; }二分试商能成立的前提是y * mid关于 mid 单调递增。这个显然成立因为 y 是非负的。但要注意 mid 的范围是[0, BASE-1]如果 y 很小、余数很大商可能会超过 BASE-1——不会因为在长除法里每次落一位之后余数一定小于 y * BASE所以商一定小于 BASE。rem.a.insert(rem.a.begin(), x.a[i])这一句是 O(n) 的插入看起来低效但对正确性没影响。如果你的数据规模很大可以改成给 rem 预留长度、用下标写入的方式能省掉内存搬移。我在实际代码里就是把 rem 当成定长数组管理的不过为了笔记可读性这里保留了直观写法。4. 性能这条线压位、Karatsuba 与阈值实测4.1 竖式乘法到底慢在哪里竖式乘法的时间全部花在内层循环那一次乘加。对于 n 个元素的数组内层循环执行 n² 次每次包含一次乘法、一次加法、一次取模、一次除法。取模和除法的开销大致是乘法的几倍所以整体常数不小。对工程实践来说真正关心的不是 n² 这个渐进式而是“多少位以内能在可接受时间内算完”。我在手头那台开发机上做过一组粗糙的测量用万进制竖式乘代码就是上面那段没有做任何特殊优化十进制位数数组长度万进制内层循环次数实测耗时1 千2506.3 万小于 1 毫秒1 万2500625 万约 6 毫秒5 万125001.56 亿约 350 毫秒10 万250006.25 亿约 1.5 秒50 万12500015.6 亿一分钟以上这组数据不是精确基准机器状态、编译选项、缓存命中都会影响但量级关系是可靠的。可以看出1 万位以内竖式完全够用10 万位开始变得难受50 万位基本没法接受。这就是为什么在真正需要处理超长数字的场景里人们会去研究更快的乘法。还有一个容易被忽略的因素内存访问。内层循环里z.a[i j]是顺序访问x.a[i]在外层固定y.a[j]顺序访问缓存友好度其实不错。但z数组会反复被读改写如果数组长度超过 L3 缓存每次读写都要走内存性能会断崖式下降。我在 50 万位那组数据上就观察到了这个现象——按循环次数算理论上应该只比 10 万位慢 25 倍实际慢了 40 倍以上。4.2 压位能带来多少提升前面算过万进制相对十进制提速 16 倍。这个数字我实测验过同一段竖式乘法逻辑一份用十进制数组一份用万进制数组算 1 万位的数十进制那份要 90 毫秒左右万进制 6 毫秒左右比例接近 16和理论吻合。为什么压位这么划算因为它是“免费的午餐”——算法结构完全不变只是把存储粒度从 1 位改成 k 位操作次数就降了 k² 倍。代码改动量极小主要是三处常量 BASE 从 10 改成 10000输出时除了最高位其余每节都要补零到 4 位输入时从字符串末尾往前每 4 个字符切一段。输出补零是压位最容易出 bug 的地方。假设结果是 [1, 23]也就是 23 * 10000 1 230001。如果你直接打印 1 和 23得到的是 123错了。正确做法是最高位正常打印其余位用%04d格式化void print(const Big x) { printf(%d, x.a.back()); // 最高位不补零 for (int i (int)x.a.size() - 2; i 0; --i) printf(%04d, x.a[i]); // 其余位补到 4 位 }这个 bug 我见过太多次了尤其是结果中间刚好有若干个零的时候比如 100000001万进制下是 [1, 0, 1]输出成 101 还是 100000001 全看有没有补零。注意从字符串输入大整数时也要按 4 位一组从后往前切分最后剩下的不足 4 位单独处理。不能从头往前切否则高位会错位。4.3 Karatsuba 什么时候才真正划算Karatsuba 算法是分治乘法的入门款思路是把一个 n 位的数拆成高低两半用三次规模减半的乘法拼出结果而不是四次。递推式是 T(n) 3T(n/2) O(n)解出来是 O(n^1.585)。指数从 2 降到 1.585听起来很美。但实际写起来你会发现教科书不会告诉你的一件事是Karatsuba 在 n 很小的时候比竖式还慢。原因有三递归调用有开销拆分数、合并结果需要额外的加法和数组分配三个子问题虽然规模减半但内存分配次数翻了好几倍。所以真正的实现都会设一个阈值n 小于阈值时直接切回竖式。这个阈值是多少我试过几个值用万进制数组、算 10 万位乘 10 万位粗略结果如下阈值数组长度10 万位耗时16约 1.1 秒32约 0.8 秒64约 0.65 秒128约 0.72 秒256约 0.95 秒不切纯竖式约 1.5 秒可以看到阈值在 64 附近是个比较甜的点相对纯竖式大约 2.3 倍加速。这个数字远没有 n^0.415 的理论比值那么夸张因为在 10 万位这个规模上log 因子的影响还很有限而且内存分配的开销吃掉了一部分收益。我换成预分配好缓冲区的写法之后才勉强做到 2.5 倍左右。所以我的建议很明确如果你的数据规模在 1 万位以内别碰 Karatsuba竖式加万进制足够了规模在 10 万位量级可以上 Karatsuba但要记得设阈值、预分配规模到百万位那就该考虑 NTT 那一套了Karatsuba 也救不了你。5. 高频踩坑与排查清单5.1 清零、进位、前导零三件套大整数运算的 bug 有 80% 集中在这三件事上我按出现频率排个序。第一位是结果没清零。乘法的 z 数组如果只resize不初始化里面是随机值后面累加的时候随机值和真实结果混在一起输出的数字会既像对的又像错的。用assign(n, 0)而不是resize(n)能一次性解决。我现在的习惯是所有构造 Big 的地方都用assign。第二位是进位没消化完。加法里数组多开一位就是为这个乘法里内层循环条件写|| carry也是为这个除法里余数最后要单独返回。这三处的处理方式不同但本质都是“进位/余数不会自动消失必须显式处理”。第三位是前导零。大整数的长度是所有逻辑的基础如果结果存在高位零长度就虚胖了。后果很隐蔽比较大小会错、输出会多打印一堆零、后续运算会变慢但结果可能还是对的——最后这条最要命因为测试用例可能刚好覆盖不到。void trim() { while (a.size() 1 a.back() 0) a.pop_back(); }注意条件里的a.size() 1不能写成!a.empty()。因为数值 0 的合法表示就是[0]如果把长度削到 0后面所有访问a.back()的地方都会崩。5.2 输出与前导零除了压位的补零还有一个常见问题是“零值输出”。如果结果就是 0而你在减法里用 trim 把长度削到了一个元素输出 0这是对的但如果某个中间结果被削成了空数组输出就是空字符串评测机会判格式错误但不会告诉你为什么。另一个问题是负数的输出。如果你实现了符号位输出时要先判断符号再打印绝对值且要特别注意“负零”的情况两个相等的数相减结果是 0如果符号位逻辑写错会输出 -0。我的做法是在减法里统一处理——如果cmp(x, y) 0直接返回 Big(0)符号位置 false。5.3 边界与内存几个必须单独测的边界0 加 0、0 减 0、0 乘任何数、被除数为 0、除数为 1、两个数相等、位数差一位比如 1000 和 999。位数差一位是最容易出问题的因为进位链会跨过整个数组。999 1、1000 - 1、9999 1 这三个用例我建议写进每次的回归测试里它们能覆盖数组扩容、进位连锁、借位连锁三种情况。内存方面大整数运算是典型的“小数据看不出问题、大数据直接崩”的类型。乘法要开x.size() y.size()的空间除法里每次试商都会产生临时 Big递归里会叠加。如果你在循环里反复做大整数乘法比如算 10 万位的阶乘那临时对象的分配次数是百万级的光内存分配就能把你拖死。解决办法是预先分配好缓冲区把临时结果传引用进去。6. 一套可以直接抄的实战流程6.1 模板准备顺序我现在的习惯是按这个顺序写先写结构体和构造函数再写 trim 和 cmp然后写加减最后写乘除。这个顺序不是随便定的因为 cmp 是减法、除法、比较的基础没有它后面全是错的加减是乘除的子过程Karatsuba 里全靠加减先把加减测通乘法出错时你才能确定问题在乘法本身。写完一个函数就立刻测一个别攒着一起测。大整数运算的错误会互相掩盖乘法错了你用除法去验证除法的结果也不对你根本不知道是哪个错了。6.2 用阶乘和 2 的幂做回归测试阶乘是最好的测试用例因为它同时覆盖乘法、进位、长度增长。2 的幂也好用因为它的十进制表示有规律你可以直接肉眼检查。Big fact(int n) { Big r(1); for (int i 2; i n; i) r mulSmall(r, i); return r; }100! 是 158 位200! 是 375 位1000! 是 2568 位。这三个规模分别对应“小、中、大”跑一遍看输出长度对不对能快速筛掉明显的 bug。如果长度对但值不对基本就是进位或者进位链的问题。6.3 与 Python 大整数对拍这是我最推荐的一步也是很多人懒得做的一步。Python 的 int 是天生的任意精度整数你拿它当标准答案把自己的 C 实现跑一遍随机数据两边一比就知道对不对。import random, subprocess for _ in range(200): a random.randint(0, 10**500) b random.randint(1, 10**300) # 把你的程序输出和 a * b 比一比具体做法是把 C 程序改成从标准输入读两个大整数字符串输出运算结果然后 Python 生成随机数据、调用子进程、比对。500 位以内的数Python 算起来是瞬间的事200 组数据几秒钟就跑完了。对拍的价值在于它能覆盖你根本想不到的边界。我曾经写过一个减法所有手写用例都过对拍跑到第 37 组才崩——那组数据是 10000 减 9999万进制下高位刚好产生了一串零trim 之后长度变成 1后面某个地方访问了a[1]。这种用例靠人想是想不出来的。6.4 一个检查清单最后把我自己在提交前会过一遍的检查项列出来都是被坑出来的乘法结果数组初始化用assign(n, 0)不是resize(n)加法数组长度取max 1减法的前置条件x y是否保证不保证时符号是否处理trim 的条件是size() 1输出最高位不补零其余位补到 W 位压位输入时从字符串末尾往前按 W 切除法里 mid 的上界是BASE - 10 的各种运算单独测一遍这套流程走下来我不敢说能写出零 bug 的实现但至少能在提交前把 90% 的低级错误挡掉。剩下那 10%交给对拍。我个人在实际操作中的体会是大整数运算真正的难点不在算法本身而在“状态管理”——进位、借位、长度、符号这四个状态贯穿所有运算任何一个在某个分支里忘了更新就会变成只在特定数据下出现的幽灵 bug。所以与其追求写法上的精巧不如把每个函数都写成“先算干净、再 trim、再返回”的固定套路让每个分支的状态都收敛到同一个地方。压位和 Karatsuba 那些优化等你把基础版本对拍跑通了再去动否则你连是优化写错了还是原逻辑错了都分不清。
