写这篇文章之前我先说个背景。前几天有个学弟发消息问我“为什么我写的高精度乘法12乘12算出来是24我用int数组存的每一位按理说思路没问题。”我一看截图就明白了——结果数组长度开小了最高位的进位直接被丢弃了。这种问题在刚接触高精度算法的人里非常普遍几乎每周都能遇到。信息学奥赛一本通里的1307题【例1.3】高精度乘法就是这么一道“看似简单但细节很多”的入门题。网上搜到的题解大多只贴代码不讲原理新手抄完能过样例换个数据就崩。这篇博文我打算把高精度乘法从头到尾拆开讲透包括为什么需要它、大数怎么存、竖式原理怎么变成代码、最容易踩的坑在哪几个地方以及从这道题延伸出去的优化路径。无论你是刚学C的初学者还是准备信息学竞赛的选手这篇文章应该都能帮到你。1. 为什么需要高精度乘法int、long long的边界与溢出真相先聊一个最根本的问题C自带的数据类型明明能存整数为什么非要自己造一套大数运算方案1.1 从13!说起内置整数类型到底能存多大随手列一下C里常用的整数类型的范围类型占用字节取值范围int4-2147483648 ~ 2147483647unsigned int40 ~ 4294967295long long8-9223372036854775808 ~ 9223372036854775807unsigned long long80 ~ 18446744073709551615int最大也就21亿左右也就是10位数。long long大得多能到19位左右。看起来挺大对吧但实际用起来根本不是那么回事。我举个例子计算30的阶乘也就是1×2×3×…×30。我大一刚学递归的时候写过这个程序用long long存结果算到20!的时候还正常20!是2432902008176640000没问题。等到21!long long直接溢出了结果变成一个很奇怪的负数。我当时的表情就是啊这也能溢出实际上21! 51090942171709440000这个数有20位long long根本顶不住。而竞赛里经常要算50!、100!甚至1000!那更不用说了。1.2 溢出为什么会出现负数补码回绕的机制很多新人对“溢出后结果变成负数”这件事非常迷惑。简单解释一下整数在计算机里以二进制补码形式存储比如int类型的2147483647二进制是01111111 11111111 11111111 11111111。当你再加1理论上应该是10000000 00000000 00000000 00000000但这个二进制在补码解释下是-2147483648。这就是传说中的“回绕”。可以理解成汽车的里程表99999再走1公里又变回00000只是整数还牵扯到符号位所以看起来像是“从最大值跳到了最小值再继续减”。所以高精度乘法的核心思想特别简单粗暴既然一个变量存不下大数那我就用数组一位一位地存。存1000位的数就开一个长度为1001的数组。1.3 高精度乘法到底解决什么问题把“大数”存下来只是第一步更重要的是让这些“大数”可以参与运算。高精度加法、减法、乘法、除法、取模本质上都是“用数组模拟人手算的过程”。在信息学竞赛里高精度运算几乎是数论题的前置技能。比如组合数C(n,m)特别大的时候、大数阶乘、大数斐波那契数列、快速幂配合大数取模等等都离不开它。所以1307这道题虽然只是一个“例1.3”但它是整个高精度运算体系的地基。这道题的具体要求我用大白话描述一下输入两个很大的正整数输出它们的乘积。有多大呢不给你设上限哪怕1000位也行。这个需求用内置类型肯定做不到必须自己写算法。2. 大数存储方案为什么要“倒着存”而不是“正着存”高精度乘法第一步是把大数读进来。但C读入的是字符串你怎么把字符串转成数组转成数组之后是正着放还是倒着放很多新手在这里栽了跟头。2.1 字符串到数组的转换假设输入的数字是“123456789123456789”先放到一个string变量里然后遍历每一位把字符转成数字string s; cin s; for (int i 0; i s.size(); i) { a[i] s[i] - 0; }这里0是一种很经典的写法。C里字符0对应ASCII码481是49依此类推。用s[i] - 0就能把字符转换成本身的数值。很多初学者会写成s[i] - 48这个也行但写0的好处是语义清晰而且不管什么编码体系下都成立。2.2 正序存储的麻烦如果直接把字符串的第0位存进数组的第0位也就是正序存储那么“123456789”就存成下标012345678值123456789看起来挺顺的但做乘法的时候麻烦就来了。你想象一下竖式乘法我们要从个位乘起个位在数字的最右边也就是数组下标最大的位置。如果正序存你每次都要从数组末尾倒着往前面处理而且进位的时候会往左边更高位进这个“左边”对应数组下标更小的位置。方向是反的很容易把下标搞混。2.3 倒序存储让个位对齐下标0最常用的做法是倒序存储。把字符串从右往左读个位放到数组下标0十位放下标1以此类推int len s.size(); for (int i 0; i len; i) { a[len - 1 - i] s[i] - 0; }这样“123”存到a数组里就是下标012值321a[0]是个位3a[1]是十位2a[2]是百位1。为什么要这么做因为乘法进位是往更高位进的而更高位对应数组下标更大的方向。倒序存储以后从下标0开始往高位走每一步都是“低位到高位”和进位的流动方向完全一致。排列整齐代码写起来也顺。我在实际教学里经常打一个比方倒序存储就像你把一摞盘子从下往上数最底下是十位、百位还是千位你不需要关心你只需要知道最上面是前段时间放上去的就行。程序处理进位的时候永远可以“从下标0开始往右走”不必担心方向问题。2.4 用定长数组还是vector在竞赛里两种写法都很常见// 写法一定长数组 int a[10005], b[10005], c[10005]; memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); memset(c, 0, sizeof(c)); // 写法二vector动态扩容 vectorint a(lenA), b(lenB), c(lenA lenB 1);个人建议在信息学竞赛场景下如果题目明确说输入不超过某个长度直接用定长数组省一点创建vector的开销如果你在做项目或者追求代码的泛用性用vector更安全因为它可以根据输入长度动态调整而且自带初始化0。但这两种在性能上没有本质差异真正影响性能的是算法本身。3. 竖式乘法的代码化从123×456到两层for循环这一节是全文的核心。我先把手工竖式怎么算说清楚再把它翻译成代码。3.1 用“123×456”完整推演一遍拿起纸笔算一下123×456但咱们换个顺序按照每一位拆开算123 × 4 492这是百位部分123 × 5 615这是十位部分123 × 6 738这是个位部分再把它们错位相加123 × 456 --------- 738 ← 123×6个位对齐 6150 ← 123×5十位对齐所以后面有个0 49200 ← 123×4百位对齐所以后面有两个0 --------- 56088看到了吧手工竖式的本质是把456拆成400506分别和123相乘然后把结果错位加起来。现在换个角度思考。如果用数组表示123倒序存储是a[0]3, a[1]2, a[2]1b[0]6, b[1]5, b[2]4123的第1位下标0值3其实代表3×10^0。456的第1位下标0值6代表6×10^0。3×618这个18应该在10^0的位置上也就是数组C[0]的位置。123的第2位下标1值2代表2×10^1。456的第1位下标0值6代表6×10^0。2×612但别忘了2是十位所以实际是20×6120也就是12×10^1应该放在C[1]的位置。总结出一个规律a的第i位乘以b的第j位结果是c的第ij位。这就是高精度乘法最核心的公式。c[ij] a[i] * b[j];3.2 核心代码逐行拆解基于上面的公式朴素高精度乘法的完整逻辑是这样的for (int i 0; i lenA; i) { for (int j 0; j lenB; j) { c[i j] a[i] * b[j]; } } // 统一处理进位 for (int i 0; i lenA lenB; i) { if (c[i] 10) { c[i 1] c[i] / 10; c[i] % 10; } }第二步是“统一处理进位”。这里有个重要细节很多人会写成边乘边进位就是在内层循环里发现c[ij]大于10就马上进位。这样做当然也行但进位可能导致前一位又超过10又得再进代码会变得很难看。更好的思路是先把所有乘积一次性累加到c数组里等到两层循环都结束再从低位到高位统一扫地式进位。这个方法数学上是完全等价的因为加法满足交换律和结合律先算1812…所有积加起来不管多大最后一次性拆成每一位。比如某一位累计到了98那就往高位进9自己剩下8。如果高位本来就有数加上这9之后又超过了10没关系等处理到那个高位的时候它自己会再往后进。3.3 c数组的长度为什么是lenAlenB1我遇到最多的疑问是为什么结果数组要开这么大两个数相乘结果最多有几位结论是lenA位的数乘以lenB位的数结果最多有lenAlenB位。最极端的例子99×9998012位数乘2位数等于4位数正好是221×111位乘1位等于1位比11小。所以lenAlenB是理论上限。那为什么还要1因为进位的时候可能“多冒出来”一位。比如在统一进位的过程中最高位c[lenAlenB-1]如果超过10就会往c[lenAlenB]进一位。所以要么数组多开一位要么进位循环的范围多走一步否则就会下标越界。3.4 完整代码这一版可以直接运行把前面所有逻辑拼起来得到一个最基础但完全正确的版本#include iostream #include string #include vector using namespace std; int main() { string s1, s2; cin s1 s2; int lenA s1.size(), lenB s2.size(); vectorint a(lenA), b(lenB); // 倒序存储 for (int i 0; i lenA; i) { a[i] s1[lenA - 1 - i] - 0; } for (int i 0; i lenB; i) { b[i] s2[lenB - 1 - i] - 0; } vectorint c(lenA lenB 1, 0); // 核心乘法 for (int i 0; i lenA; i) { for (int j 0; j lenB; j) { c[i j] a[i] * b[j]; } } // 统一进位 for (int i 0; i lenA lenB; i) { c[i 1] c[i] / 10; c[i] % 10; } // 去掉前导零并输出 int pos lenA lenB; while (pos 0 c[pos] 0) pos--; for (int i pos; i 0; i--) { cout c[i]; } cout endl; return 0; }这里我用vector而不是定长数组是因为输入长度未知时vector更省心。vectorint c(lenA lenB 1, 0)一行代码就完成了长度定义和清零初始化比memset更符合现代C习惯。3.5 测试几个用例验证一下我强烈建议写完代码先测几组“能用手算算出来”的数据确认逻辑正确后再去测大数据。我自己常用的测试数据是输入输出说明123 45656088基础三位数乘法999 999998001连续进位检查0 123450前导零处理检查100 10010000中间零检查1 11最小输入检查特别是“0 12345”这一组很多新手写的代码在这里翻车因为结果数组里全是零输出的时候如果不处理会输出比如“0000000”这样一堆零或者干脆什么都输出不了。这个在下一节重点讲。4. 最容易翻车的细节前导零、下标错位与进位残留很多人的高精度乘法代码“看起来一模一样”但就是WAWrong Answer。我把这几个最常见的坑按出现频率排个序一个个说。4.1 前导零为什么输出“00056088”或者什么都不输出如果两个数相乘结果是0比如0×12345那么c数组所有位置都是0。这时候如果用循环从高位直接输出就会输出一长串零而不是一个0。如果输入不是0但中间某一位恰好是0比如100×10010000倒序存储时c数组可能是c[4]1, c[3]0, c[2]0, c[1]0, c[0]0。从高位c[4]输出没问题但问题在于c数组的实际长度是lenAlenB1也就是516。c[5]是多余的值是0。如果不处理就会输出“010000”。我见过更离谱的写法从lenA lenB - 1开始输出结果数字少了一位比如123×456算出来变成6088。为什么因为结果长度其实是5位56088而lenAlenB-14计数方式差了1。正确处理方式是从后往前找到第一个非零位置从这个位置开始往低位输出。代码我已经写在上面了int pos lenA lenB; while (pos 0 c[pos] 0) pos--; for (int i pos; i 0; i--) { cout c[i]; }4.2 这个坑我经常见下标ij写错核心循环里最容易出的错是把c[i j]写成c[i * j]或者c[i j - 1]。c[i * j]是数学直觉上的错误——你把“位权相加”理解成“下标相乘”了。我当年写第一版高精度乘法时也犯过这个错因为觉得“两个数的位数相乘应该用乘号”。但实际上位数对应的指数是相加的10^i × 10^j 10^(ij)所以下标必须相加。c[i j - 1]则是手滑看起来差不多但全错。如果出现这种问题建议在小数据上手动模拟一遍立刻就能暴露。4.3 进位处理不彻底每一位只进一次就结束还有一种隐蔽错误进位循环只处理了前lenA位没处理到结果的最高位。比如for (int i 0; i lenA; i) { c[i 1] c[i] / 10; c[i] % 10; }只循环到lenA如果乘积很长高位根本没有机会进位。结果就是中间会出现大于9的数字输出崩溃。正确做法是循环到lenA lenB这样即使最高位又产生新的进位也有空间可以放。另一个可能出错的写法是for (int i 0; i lenA lenB; i) { if (c[i] 10) { c[i 1] c[i] / 10; c[i] % 10; } }加了if判断没有错但它隐含了一个假设c[i]进位后一定小于10。如果进位的数量特别大比如c[i]是900那c[i] % 10确实让这一位变成0但c[i1]会变成90循环到i1的时候又会处理。所以加了if其实是安全的只是多写了一个判断条件。不过为了简洁我更推荐不加if直接整除取模让每一位都过一遍“进位数余数”逻辑更统一。4.4 你遇到“结果输出成负数”时先查这三处有些读者反馈说自己的高精度乘法用int数组存结果输出全是负数。这种情况几乎可以肯定是数组越界访问了。数组越界的表现很迷惑有时候是输出乱码有时候是负数有时候什么都不输出直接崩掉。排查方法是打开编译器的AddressSanitizer或者用-fsanitizeaddress重新编译g -fsanitizeaddress -g bigmul.cpp -o bigmul运行以后如果数组越界程序会直接告诉你哪一行越界了不用自己瞎猜。4.5 手把手复现一次完整排查12×12为什么会输出24回到文章开头那个学弟的问题。我按他的代码测试了一下发现12×12输出24。如果你也遇到类似的问题按下面步骤排查第一步确认输入存储正确。把a和b数组打印出来a应该是[2, 1]b应该是[2, 1]。如果这里就不对说明倒序部分写错了比如下标转换公式有误。第二步模拟乘法循环。i0, j0c[0] 2×24i0, j1c[1] 2×12i1, j0c[1] 1×22i1, j1c[2] 1×11。所以正确情况下c数组应该是[4, 4, 1]从后往前输出就是144。如果输出24说明c数组长度不够。最常见的错误写法是vectorint c(lenA lenB - 1, 0)这样c数组只有3个位置下标0/1/2按理说也能放下144。但有些编译器对vector的越界访问不报错只是静默覆盖相邻内存导致c[2]的值被其他数据覆盖成0了。还有一种可能是输出循环写成了for (int i lenA lenB - 2; i 0; i--)从下标1开始输出把最高位漏掉了。所以遇到这种“少一位”的bug先查结果数组长度再查输出起始位置绝大多数情况下是这两个问题之一。5. 从朴素算法到压位优化高精度乘法的性能进阶1307这道题如果只是过题前面的写法已经完全够了。但如果你的目标是竞赛拿奖或者要处理上万位的数字朴素的O(n²)算法是不够看的。这一节聊一下性能优化的几个方向。5.1 朴素算法的时间复杂度到底是多少两个长度分别为n和m的数相乘核心代码是两层循环时间复杂度O(n×m)。假设两个数都是10000位那就是10^8次乘法在竞赛1秒时限内很吃力超过2秒也正常。如果位数到50000那就要2.5×10^9次彻底没戏。5.2 一个容易忽略的优化点中间结果要用更大的类型在普通十进制一位一存的版本里c[ij] a[i] * b[j]这一步a[i]和b[j]都是0~9乘积最多81加上原有的c[ij]理论上限不超过81×max(n,m)对于int完全够用所以int不会溢出。但如果你做“压位”让每个数组元素存一个更大的数比如每个位置存0~9999那么乘法时每个元素可以到9999乘积最大接近1亿。两个这样的乘积累加int就不一定扛得住了。所以压位版本最好用long long类型存储中间数组或者至少用long long来做乘法运算再存回int。这是一个非常容易踩的坑因为普通版本不溢出换个压位写法就溢出而且溢出的表现是“答案莫名变成负数”或者“某一位答案差一点”。5.3 压位为什么能快4倍以上十进制每一位只存0~9实际上非常浪费数组空间和循环次数。我们可以把数组的每一位当成“10000进制”的一位也就是说a[0]存的不再是个位而是10^0到10^3四位a[1]存10^4到10^7四位以此类推。这样同样大小的数组能存储4倍的位数而乘法的两层循环次数直接除以16因为每个维度都缩到1/4乘积是1/16。再加上进位处理也变少整体性能提升不止4倍。压位版本的核心代码长这样const int BASE 10000; for (int i 0; i lenA; i) { for (int j 0; j lenB; j) { c[i j] a[i] * b[j]; c[i j 1] c[i j] / BASE; c[i j] % BASE; } }注意这里我用了long long数组来保证中间运算不溢出vectorlong long c(lenA lenB 1, 0);输出压位结果时有个大坑不是直接遍历输出因为每个元素存的是四位十进制数如果直接用cout c[i]对于本质上是“0001”这样前导零的部分会丢零。比如10000这个数倒序存为c[1]1, c[0]0正序输出时最高位是c[1]输出1然后c[0]要输出成“0000”而不是“0”。正确的输出方式int pos lenA lenB; while (pos 0 c[pos] 0) pos--; cout c[pos]; // 最高位不用补零 for (int i pos - 1; i 0; i--) { printf(%04lld, c[i]); }%04lld的意思是输出至少4位不足4位左边补0。这是压位高精度的经典细节能在OJ上卡住一大批人。5.4 分治乘法与FFT给你指个方向在压位之上还有两条进阶路线第一条是Karatsuba分治乘法。核心思想是把两个大数各分成高低两半原本需要4次乘法通过一些代数技巧只做3次乘法递归下去时间复杂度从O(n²)降到O(n^1.585)。实现难度中等在位数几千~几万时很有效。第二条是FFT/NTT快速傅里叶变换。把两个大数看作两个多项式的系数数组乘法就是多项式卷积。用FFT在O(n log n)时间内完成卷积直接在竞赛中处理10万位以上的乘法。但FFT涉及复数、精度误差NTT虽然用整数模运算避免了精度问题但需要处理模数和原根代码复杂度至少100行起步不建议刚接触高精度的人直接扑上去。我个人的学习路线建议是先把朴素的十进制一位版本写到滚瓜烂熟理解数组和进位的本质。再写压位版本理解空间换时间、格式化输出的细节。如果你在准备提高组或者省选再考虑Karatsuba。FFT留到大学算法课或者钻研组合数学题再碰不必急于一时。6. 从一道例题到一个工具库高精度运算的工程化封装题目做完了代码也AC了但这就是终点了远不是。1307题只是高精度乘法的入门在真实的信息学竞赛题目里你永远不会只做一次乘法通常还要连带加法、减法、比较大小、取模甚至除法。所以最聪明的做法是把这些运算封装成一个类或者至少封装成几个独立函数到时候直接调用。6.1 一个HighPrecision类的骨架设计我不建议一上来就把类设计得特别复杂。对新手来说一个类里面至少有这几个成员vectorint digits倒序存储每一位的数字。bool negative符号位处理负数用。构造函数接收string或者int。成员函数add、subtract、multiply、compare如果想挑战还可以加divide和mod。一个简化版的类头部长这样class BigInt { private: vectorint digits; // 倒序存储 bool negative; public: BigInt(string s); // 字符串构造 BigInt(long long num); // 整数构造 string toString(); // 转回字符串输出 bool operator(const BigInt other) const; BigInt operator(const BigInt other) const; BigInt operator-(const BigInt other) const; BigInt operator*(const BigInt other) const; };重载运算符的好处是用法跟内置整数类型一样a * b直接得到BigInt类型的结果不用每次调用函数都很啰嗦。6.2 乘法运算符的重载实现乘法的实现跟之前的算法一模一样只是披了一层类的壳BigInt BigInt::operator*(const BigInt other) const { int lenA digits.size(), lenB other.digits.size(); vectorlong long temp(lenA lenB 1, 0); for (int i 0; i lenA; i) { for (int j 0; j lenB; j) { temp[i j] (long long)digits[i] * other.digits[j]; } } // 统一进位 for (int i 0; i lenA lenB; i) { temp[i 1] temp[i] / 10; temp[i] % 10; } // 去掉前导零确定最高位 int pos lenA lenB; while (pos 0 temp[pos] 0) pos--; BigInt result; result.digits.resize(pos 1); for (int i 0; i pos; i) { result.digits[i] (int)temp[i]; } result.negative negative ! other.negative; return result; }这个类虽然小但你把加法、减法、比较封装进去以后很多题目就能直接当模板用。6.3 除法怎么办高精度除法的入门思路高精度除法比乘法和加法都难。最简单的一种是高精度除以低精度即被除数是大数除数是int思路是模拟手算竖式的“试商”过程从最高位开始每次取当前位加上余数×10除以divisor得到商的这一位余数保留到下一位。vectorint divide(const vectorint a, int divisor, int remainder) { vectorint quotient(a.size(), 0); long long cur 0; for (int i a.size() - 1; i 0; i--) { cur cur * 10 a[i]; quotient[i] cur / divisor; cur % divisor; } remainder (int)cur; // 去掉前导零 while (quotient.size() 1 quotient.back() 0) quotient.pop_back(); return quotient; }高精度除以高精度更复杂常用做法是“二分乘法验证”或者“竖式模拟”。在当前阶段如果你能在1307题的基础上把加法、减法、乘法、模低精度写出来应对大部分入门到中等题目已经够用了。6.4 场景延伸高精度乘法在实际题目中怎么出现信息学竞赛中高精度很少单独成题更多是作为某个复杂题目中的一个环节出现。举几个典型场景大数阶乘计算n!朴素思路是循环乘i每次用高精度乘低精度。n到1000时结果有2500多位用高精度乘法非常自然。斐波那契大数F(1000)已经是一个208位的数了想继续算下去就需要高精度加法。组合数C(n, k)如果n和k都很大但结果更大先约分再高精度乘除避免中间结果溢出。大数快速幂底数和指数都是大数时要用到高精度乘法和取模。所以学完这一道题建议趁热打铁把加法、减法、比较大小也写了凑成一套属于你自己的小工具库。以后在OJ上碰到大数题直接从自己的库里复制比每次临时翻题解高效得多。7. 新手到熟练的进阶路径代码之外的三个能力最后聊点代码之外的东西。我见过太多人刷题只看题解复制代码AC了就算完事。但高精度乘法这种基础算法真正拉开差距的地方在于“你是否理解每一步的为什么”和“换一种写法你还能不能写出来”。7.1 用三种不同的数据结构各写一遍同样的高精度乘法我建议你至少写三遍第一遍定长数组int memset这是最贴近竞赛机考环境的写法。第二遍vector 动态长度掌握现代C对数组的替代方案。第三遍压位版本体会同样的算法代码量翻倍但性能提升明显。三遍下来你对这个算法的理解会从“背代码”变成“理解本质”。7.2 学会用对拍验证你的高精度运算写大数算法最怕的是样例全过、大数据全错。正确的验证方式是写一个小工具用Python或者系统自带的bc命令计算大数乘法然后和你的C程序输出做对比。比如Linux下可以echo 123456789123456789 * 987654321987654321 | bc或者写个Python脚本随机生成大数进行对拍。这种自动化测试方法在入门阶段看起来有点小题大做但它能帮你用非常低的成本在几十几百组随机数据中快速发现问题比手动试数据高效太多了。我在写高精度运算的时候遇到过很多次“所有手算例子都对一提交就WA”的情况。后来发现都是边界条件——比如有前导零、一个数是0、两个数位数相差极大等。这些情况单靠手工测试很难覆盖全尤其是两个数一长一短的时候很多人的下标逻辑会出问题。7.3 从“会做”到“会讲”最后给你一条很实用的小建议找一位同学尝试把高精度乘法的原理跟他讲清楚。如果你讲解过程不卡壳说明你真的理解了。如果讲到进位处理时对方一脸茫然大概率是你自己也还差一层窗户纸没捅破。我在带教学弟学妹的过程中经常发现“讲一遍”比“写十遍”更能暴露出理解上的漏洞。这不丢人反而是成长最快的方式。高精度乘法这道题看似只是一个简单的数组模拟但里面藏满了细节存储布局、进位的时机、前导零处理、边界长度、压位思想每一个点将来都会在更复杂的题目中出现。吃透这一道等于把整个高精度体系的地基打牢了。接下来无论做大数加法、大数除法还是基于大数的数论题你都会觉得顺手很多。