C里搞高精度算法说白了就是绕开 int、long long 这些内置整型的长度限制用数组、字符串或者 vector 把大数拆开一位一位存再按手算竖式的思路模拟加减乘除。不少入门的朋友一听到“突破整型限制”就觉得是是什么高大上的数学技巧实际上它就是一组“用空间换范围”的工程手段。今天这篇东西我直接以 C 为语言环境从存储结构讲起把加、减、乘、除、阶乘、快速幂这套完整过一遍顺便把我在调试和性能优化时踩过的坑也一并记录下来。文章适合刚学 C、准备算法竞赛或者工作中偶尔要处理超大整数运算的开发者看完你至少能自己写一份能跑、可扩展的高精度模板。1. 整型的上限与高精度算法的设计逻辑1.1 内置整型到底能存多大C 里内置整型的范围是很多人容易忽略的“隐形天花板”。int 通常是 32 位范围是 -2147483648 到 2147483647也就是最多 10 位数unsigned int 翻一倍但还是只有 42 亿多。long long 一般是 64 位能到 9223372036854775807看着挺大其实也就 19 位数。我们再看两个实际场景100 的阶乘大约有 158 位斐波那契数列第 100 项已经超过 20 位数RSA 加密里要处理的模数动辄 1024 位以上。这些数字靠 long long 根本装不下强行用 double 又会有精度丢失。所以高精度算法干的事情就是“拆数”。把一个 100 位的大数拆成 100 个 0 到 9 的数字按顺序放进数组里再用我们小学就学过的竖式方法做运算。单个数字的运算永远不可能溢出每一位的进位和借位也都是小范围操作这样整体上就突破了内置整型的限制。这里顺便说一句很多人问“用 Python 不就没这个问题了吗”。确实语言层面自带大整数会省事很多但 C 里你还是得懂这层逻辑。一方面算法竞赛里 C 是大头高精度是基本功另一方面自己手写一遍会让你彻底明白计算机是怎么处理超出字长的数值的。面试时被问到“大数相加怎么实现”本质考的就是这个。1.2 数组模拟竖式的核心思想高精度最核心的两个设计决策用什么结构存数以及为什么低位放在数组前面。我用的是vectorint配合“低位在前”的存储方式。举个例子整数 12345 存进数组时顺序是[5, 4, 3, 2, 1]a[0]是个位a[1]是十位依此类推。这样设计的理由是加法和乘法产生的进位只会向高位扩散也就是数组的下标越来越大。如果采用“高位在前”的存储每次进位都得在数组头部插入元素时间复杂度会退化到 O(n)很痛苦。低位在前进位就变成了push_back操作摊还复杂度是 O(1)。有人可能会建议用字符数组或者string存储字符串的好处是不用处理输入时的大小写转换直接从0减到0就行。但字符串做中间运算时进位和借位要反复修改字符而且下标处经常出现需要转换成数字的麻烦。实战下来vectorint是最顺手的因为元素本身就是整数加减运算不用做 ASCII 转换而且后面做压位优化时一个元素可以直接存 0 到 9999 的大数用vectorint天然支持这种改造。还有一个细节高精度算法里数字 0 的表示要统一。我习惯用vectorint只存一个 0。减法、除法做完后如果结果全部为 0至少保留一个元素避免输出空字符串。这个边界问题在后面会反复出现。2. 基础运算的全实现字符串转数组、加法、减法2.1 从字符串到高精度数组的读写在做任何运算前先要解决两件事把输入字符串转成高精度数组把高精度数组转回字符串输出。这两步看着简单但不少 bug 都埋在这。下面这段代码我用了很久逻辑非常直接#include bits/stdc.h using namespace std; // 字符串 - 高精度数组低位在前 vectorint load(const string s) { vectorint a; for (int i s.size() - 1; i 0; --i) { a.push_back(s[i] - 0); } if (a.empty()) a.push_back(0); return a; } // 高精度数组 - 字符串去掉前导零 string to_string_big(const vectorint a) { int pos a.size() - 1; while (pos 0 a[pos] 0) --pos; // 至少保留一位 string res; for (int i pos; i 0; --i) { res.push_back(char(0 a[i])); } return res; }load里倒序遍历字符串把每个字符转成数字后再push_back这样低位天然就落在数组头部。to_string_big则从尾部高位开始找第一个非零元素如果全部是 0也保留最后一位所以输出永远是“0”不会输出空串。这里我要提醒一个容易出错的地方如果你从键盘读入的数字本身就带换行、空格或者是有符号的负号“-”上述load函数会因为无法处理符号而错乱。我的做法是读入整体字符串后先判一下首位是不是-如果是就单独记录符号标记再把剩余部分传入load。后面的比较、减法也已经考虑了符号维度但在基础模板里可以先只做非负数避免一上来就被负号搞晕。2.2 高精度加法进位处理与模板高精度加法是最容易上手的运算。原理就是竖式从低位到高位把两个数对应位相加加上来自低位的进位然后取个位作为当前结果位十位作为下一位的进位。循环结束后如果最高位还有进位再补一位。代码写出来非常紧凑// 高精度加法支持不同长度的 vector vectorint add(const vectorint a, const vectorint b) { vectorint c; int carry 0; int n max(a.size(), b.size()); for (int i 0; i n; i) { int sum carry; if (i (int)a.size()) sum a[i]; if (i (int)b.size()) sum b[i]; c.push_back(sum % 10); carry sum / 10; } if (carry) c.push_back(carry); return c; }这个模板有两个关键点。第一个是sum % 10和carry sum / 10这两个操作在十进制下相当于取个位和取十位。如果以后要做 16 进制高精度这里改成% 16和/ 16就行。第二个是max(a.size(), b.size())来确定循环次数避免两个数位数不同时漏掉较长那个数的剩余位。我在新手期犯过的最臭错误就是循环写成a.size()然后两个长度不等的数相加时高的位直接被丢掉了。调试小技巧单测就用最野的边界值。0 0必须输出 099 1必须输出 100 而不是 009999999 1必须输出 10000000。这几个用例过了加法基本就稳了。很多人在进位循环结束后忘了检查carry直接返回结果导致99100这是高精度加法里出现频率第一的错误。2.3 高精度减法比较大小、借位与符号处理减法比加法复杂一点原因在于借位和符号。竖式减法是从低位开始如果当前位的被减数小于减数就要向高位借 1。实现之前必须先判断谁大谁小因为负数的竖式计算规则不是简单地“符号留给外面内部始终用大的减小的”。先看比较函数。因为高精度数组是低位在前的比较大小的逻辑是先比长度长度不同则长度大的数更大长度相同再从最高位往低位逐个比较// 返回 true 如果 a b bool greater_big(const vectorint a, const vectorint b) { if (a.size() ! b.size()) return a.size() b.size(); for (int i a.size() - 1; i 0; --i) { if (a[i] ! b[i]) return a[i] b[i]; } return false; // 相等 } // 高精度减法前提 a b结果仍为非负数 vectorint sub(const vectorint a, const vectorint b) { vectorint c a; // 拷贝一份直接在拷贝上修改 int n a.size(); for (int i 0; i n; i) { int cur c[i]; if (i (int)b.size()) cur - b[i]; if (cur 0) { cur 10; if (i 1 n) c[i 1]--; // 向高位借 1 } c[i] cur; } // 去前导零 while (c.size() 1 c.back() 0) c.pop_back(); return c; }实际的带符号减法可以这样封装先比较a和b如果a b结果符号为正直接sub(a,b)否则结果为负就sub(b,a)后在输出层打负号。不要试图在sub内部做符号会让代码变得非常难读。减法里的一个坑借位后高位可能变成负数下一轮循环会继续借位链条会一直传递下去。我写的循环里第i位借位会影响c[i1]而i1在下一轮会被再次处理所以链条是通的。但如果循环顺序写反了从高位往低位处理就会出现“借位不知道借到哪里”的混乱。这个模块写过一次就别改了我后来所有高精度工具类都直接复用这两个基本函数。3. 乘除与进阶计算从乘法到除法再到阶乘幂3.1 高精度乘法双层循环与统一进位高精度乘法比加减法上了一个台阶因为它不再是单纯的一位对一位而是要处理两位之间的交叉乘积。原理还是竖式把a[i] * b[j]的结果累加到结果的第ij位。只不过这里我们不是每乘一步就立刻进位而是先把所有乘积都累加到位上最后统一处理进位。这样做的好处是减少进位次数避免大量无意义的取模操作。核心实现如下vectorint mul(const vectorint a, const vectorint b) { int n a.size(), m b.size(); vectorint c(n m, 0); for (int i 0; i n; i) { for (int j 0; j m; j) { c[i j] a[i] * b[j]; } } // 统一处理进位 int carry 0; for (int i 0; i n m; i) { int val c[i] carry; c[i] val % 10; carry val / 10; } // 结果长度可能虚高去掉前导零 while (c.size() 1 c.back() 0) c.pop_back(); return c; }注意细节a[i] * b[j]的结果在极端情况下可能达到 9 × 9 81累加多次后c[ij]可能超过 100。在逐位存储的版本里单个 c 的元素理论上最多是 81 × 长度长度大了就可能溢出int。不过如果长度不超过两千万位int 还是够的但在压位版本里中间结果会非常大所以我会用long long做统计或者分段处理。这里为了基础版清晰先用 int但在注释里标注这是需要注意的地方。还有一个性能点这个双层循环是 O(n*m)当两个数都是 10 万位时1e10 次乘法会慢到无法接受。所以高精度乘法后续通常要接 FFT 优化我放到后面专门说。3.2 高精度除法除以单精度与除以高精度高精度除法的实现通常分两类除以一个小整数单精度和除以另一个高精度大数大数除大数。除以单精度是最简单的一种因为除数小我们可以从最高位开始逐位处理每次把当前余数乘以 10 再加上当前位的数字然后除以除数得到商的一位剩下的作为余数带入下一位。这个逻辑和手算除法的试商过程一模一样。// 返回商同时通过引用的余数返回 vectorint div_mod_single(const vectorint a, int b, int remainder) { vectorint q(a.size(), 0); long long rem 0; for (int i a.size() - 1; i 0; --i) { rem rem * 10 a[i]; q[i] rem / b; rem % b; } while (q.size() 1 q.back() 0) q.pop_back(); remainder rem; return q; }这里我想提醒一个容易忽略的问题如果被除数本身为 0除完之后返回的q可能是空 vector 或者只有 0。上面的实现先把 q 初始化为a.size()大小所以不会为空然后去前导零也保证了至少保留一位。但如果a本身就是空 vector这在我早期的模板里可能出现就要在函数开头做兜底判断。至于大数除大数最自然的方式是模拟长除法但实现起来繁琐。更实用的是二分答案法对于a / b答案 q 必然落在 0 到 a 之间我们二分 q然后用高精度乘法判断q * b是否小于等于a。这种算法复杂度是 O(n^2 log V)n 是被除数位数V 是商的大小范围。当位数不多时它比手写长除法更不容易出错。二分法代码思路大概是这样vectorint div_big(const vectorint a, const vectorint b) { // 先处理特殊情况b 为 0 直接报错这里不演示这类错误分支 vectorint low(1, 0), high a; while (!greater_big(low, high)) { vectorint mid add(low, high); mid div_mod_single(mid, 2, ?); // 高精度除以2也可以直接用移位实现 if (greater_big(mul(mid, b), a)) { high sub(mid, vectorint(1,1)); // 不能在 mid 上直接改要先拷贝 } else { low add(mid, vectorint(1,1)); } // 需要做终止条件判断这里只是演示框架 } return low; }严格来说这个二分框架里终止条件的处理要非常小心尤其是 mid 和 low/high 相邻时要防止死循环。我的经验是直接在高精度运算基础上再封装一个带幂次的比较函数然后在循环结束时多验证一次。这种方案在笔试和面试讲思路时足够用但它不是最优实现如果你要在一个高负载项目里频繁使用大数除法我更推荐去用成熟的大数库比如 GMP。3.3 经典应用大数阶乘、快速幂与组合数有了加、减、乘、除这些原语之后就可以拼装出很多实用算法了。第一个经典应用是大数阶乘。比如计算100!用 long long 存会溢出用高精度乘法循环乘就行了vectorint factorial(int n) { vectorint res(1, 1); for (int i 2; i n; i) { vectorint factor; int t i; while (t 0) { factor.push_back(t % 10); t / 10; } res mul(res, factor); } return res; }每次把当前结果乘以下一个数由于 n 本身是普通整数所以构造因子时只要用普通除法拆位即可。时间复杂度是 O(n^2) 量级n 到 10000 时已经有点慢但 n 小于 1000 时体验很好。竞赛里经常用这种方法算组合数 C(n, k)因为阶乘取模的问题会牵扯到逆元而不取模的大组合数直接高精度乘除也能做只是要把所有中间结果都控制在高精度层面。第二个经典应用是快速幂配合高精度。像计算2^100这种直接循环乘 100 次就完事但如果要算2^100000就必须用快速幂。把指数拆成二进制每次把底数平方遇到当前位为 1 就把结果乘上底数。核心代码很短vectorint fast_pow(vectorint base, int exp) { vectorint result(1, 1); while (exp 0) { if (exp 1) result mul(result, base); base mul(base, base); exp 1; } return result; }这个版本的 base 可以是高精度exp 是普通整数。如果你要算的是高精度大数的幂指数本身也是大数那么快速幂依然适用但指数的二进制拆位就需要额外处理。我一般把指数转成 uint64_t如果指数位数超过 64 位就改用高精度存储并通过高精度除以 2 来遍历二进制位。这类进阶组合的通用价值在于高精度不是孤立的一两个函数而是一个可以叠加的组合框架。你先把加减乘除这些原语写稳阶乘、幂、组合数、取模就都成了简单拼装。我在实际比赛中最常用到的正好就是“高精度阶乘 高精度组合数 高精度取模”这套组合Gym 题里的 Extended Big Number 总结基本都是这套模板。4. 常见问题与性能优化实录4.1 五个高频 bug 现场高精度算法代码量不大但出错的频率出乎意料地高。根据我自己的排错记录和帮别人 review 的经验下面五种 bug 出现频率最高我直接整理成表方便你对照自查症状根因解法99 1 输出 00加法循环结束后没有把最后的进位 push_back在循环末尾判断if (carry) c.push_back(carry)100 - 99 输出 1 而不是 10 的前导零问题去除前导零时去掉了不该去的 0或者是减法借位后某一高位变成负数但未处理先去前导零再检查借位链是否完整123 * 456 输出结果位数不对多了一位 0乘法结果的初始长度设成了 nm且去掉前导零前忘了处理尾部多余的 0统一进位后再去前导零保留至少一位一个 5000 位的数除以 7输出为空除法的结果 vector 长度初始为 0前导零删除后整条链断了初始化 q 为被除数长度并保证至少保留一位在压位版本里输出 10000 时只输出 1输出时没有对当前元素做前导补零输出模板里对非最高位元素格式化 4 位不足补零这五个 case 基本就是我在代码 Review 时最常圈出的地方。尤其是第一个“加法忘进位”几乎每个从零手写高精度的人都要踩一次。我的建议是每一个函数写完都要做一个极小的测试脚本用十组以内的高覆盖用例跑一遍不要等整套模板写完再统一调那样定位 bug 的成本会高很多。4.2 压位优化让高精度运算更快逐位存储虽然直观直观但性能确实拉胯。数组长度大循环次数多vector 的内存访问也不够友好。如果要做大规模的阶乘、大数的乘法我建议上压位。压位的思路是把几个十进制位打包进一个int里比如万进制即每个元素存储 0 到 9999 的数字这样数组长度直接减小到原来的四分之一。进位处理时用的是 10000 而不是 10模运算和除法也相应地改成 10000。这样加、减、乘的循环次数都少了四倍而且内存占用也小了cache 友好度提升明显。压位版本的关键在于输入输出。输入时不能一个字符一个字符地存而是从字符串末尾每 4 个字符切一段转成整数后作为数组的一个元素存储。输出时除了最高位那段其余每段必须用setw(4) setfill(0)补零到 4 位否则像“10000”这种数字会输出成“1 0 0”这种错位形式。压位版 load 和输出示例vectorint load_base10000(const string s) { vectorint a; int len s.size(); for (int i len; i 0; i - 4) { int start max(0, i - 4); a.push_back(stoi(s.substr(start, i - start))); } if (a.empty()) a.push_back(0); return a; } string to_string_base10000(const vectorint a) { stringstream ss; ss a.back(); for (int i (int)a.size() - 2; i 0; --i) { ss setw(4) setfill(0) a[i]; } return ss.str(); }这里的stoi在字符串段是 4 位时不会溢出最大 9999安全。进位操作则把%10改成%10000把/10改成/10000。乘法中间结果用 long long 存因为a[i] * b[j]最大约 1e8累加多次可能接近亿级别但远小于 2^63-1所以用long long做累加是安全的。压位的增益我实测过计算 30000! 时逐位版本大约需要 4 到 5 秒压位到万进制后大概在 1 秒内。这个提升主要来自循环次数减少和内存减小。如果你的比赛环境内存限制较严格压位几乎是必然选择。4.3 选型思考什么时候用现成库有些读者可能会问“C 里不是有__int128也有 Boost 的 multiprecision还有 GMP为什么还要手写高精度”这个问题我认真想过答案是看场景。__int128是 GCC 和 Clang 的扩展能直接存储 128 位整数最大约 1.7e38比 long long 大得多运算速度也接近原生整型。但首先它不是标准 C换到 MSVC 环境下就不一定能用其次 128 位的范围依然有限一旦数值超过这个界限还是得回到高精度路线。所以我的习惯是中间结果确认不会超过 128 位的就优先用__int128性能最好一旦预估位数超过几百位直接上自己写的高精度模板。Boost.Multiprecision 的cpp_int和 GMP 都非常成熟功能强大GMP 甚至在某些大整数运算上比自己写的模板快几个数量级。但引入它们往往意味着依赖管理复杂度上升比赛环境不一定预装 GMP跨平台编译也更容易出问题。写业务代码时如果只是偶尔算一个大数用 Boost 是最省心的。但如果你想真正掌握算法原理或者需要在比赛中一个压缩包跑完所有代码手写高精度仍然是必备技能。我把常见方案整理成一张对照表方案表示范围性能可移植性适合场景long long19 位十进制极快极好常规计算、索引、计数__int12838 位十进制很快较依赖编译器中间结果超过 64 位但不太离谱时手写高精度任意位数一般可压位/FFT 优化极好算法竞赛、教学、无额外依赖环境Boost.Multiprecision任意位数较好有编译头依赖业务代码、工程实践GMP任意位数极快需要编译/链接库高性能大数计算、密码学等选型时不用纠结原则就是“性能够用、依赖可控、代码可维护”。手写高精度虽然性能一般但它最大的优势是零依赖在任意环境都能跑。4.4 扩展场景高精度的应用不止算法竞赛。金融系统里金额计算为了避免浮点误差常用十进制定点存储本质上就是一种高精度只是基数换成了分、厘这类单位加密算法里 RSA、ECC 都有大量的大数高频运算区块链、哈希碰撞检测也离不开大数处理。如果你以后在业务代码里碰到“这个数字用 int 存不下”“浮点精度无法接受”这类需求高精度模板就是你的底层工具箱。再延伸一步当高精度乘法遇到百万位级的输入时O(n²) 的手写竖式乘法会显得非常吃力这时候就该引入 FFT快速傅里叶变换或 NTT快速数论变换把乘法的复杂度降到 O(n log n)。我在前文提过的手写模板在竞赛够用但真做超大乘法时还是建议去了解一下 FFT 版本的实现。这又是独立的一大块知识体系但基础的高精度原语依然通用。最后再分享一个我自己的习惯高精度模板里的add、sub、mul、div_mod_single、greater_big这几个函数我会全部做成独立函数并且参数都用const vectorint绝不直接在原参数上修改。这样一个函数出问题时单测可以精确定位到某一环而不用在几十层调用之间来回追。加法和乘法之间可以组合出幂和阶乘减法与比较、除法之间可以组合出取模和整数除这套组合真的是算法比赛里最常碰的核心工具。写高精度最容易犯的错是急着把整套代码写出来再调试。我现在的流程是先写一个逐位版本跑通所有基础用例再去写压位版本压位版本出问题时用逐位版本去对拍几乎立刻就能看出是输出格式问题还是进位逻辑问题。这个“双版本对拍”的方法帮我省了不知道多少排查时间建议你也试试。
C++高精度算法从入门到实战：突破整型上限的大数运算模板
C里搞高精度算法说白了就是绕开 int、long long 这些内置整型的长度限制用数组、字符串或者 vector 把大数拆开一位一位存再按手算竖式的思路模拟加减乘除。不少入门的朋友一听到“突破整型限制”就觉得是是什么高大上的数学技巧实际上它就是一组“用空间换范围”的工程手段。今天这篇东西我直接以 C 为语言环境从存储结构讲起把加、减、乘、除、阶乘、快速幂这套完整过一遍顺便把我在调试和性能优化时踩过的坑也一并记录下来。文章适合刚学 C、准备算法竞赛或者工作中偶尔要处理超大整数运算的开发者看完你至少能自己写一份能跑、可扩展的高精度模板。1. 整型的上限与高精度算法的设计逻辑1.1 内置整型到底能存多大C 里内置整型的范围是很多人容易忽略的“隐形天花板”。int 通常是 32 位范围是 -2147483648 到 2147483647也就是最多 10 位数unsigned int 翻一倍但还是只有 42 亿多。long long 一般是 64 位能到 9223372036854775807看着挺大其实也就 19 位数。我们再看两个实际场景100 的阶乘大约有 158 位斐波那契数列第 100 项已经超过 20 位数RSA 加密里要处理的模数动辄 1024 位以上。这些数字靠 long long 根本装不下强行用 double 又会有精度丢失。所以高精度算法干的事情就是“拆数”。把一个 100 位的大数拆成 100 个 0 到 9 的数字按顺序放进数组里再用我们小学就学过的竖式方法做运算。单个数字的运算永远不可能溢出每一位的进位和借位也都是小范围操作这样整体上就突破了内置整型的限制。这里顺便说一句很多人问“用 Python 不就没这个问题了吗”。确实语言层面自带大整数会省事很多但 C 里你还是得懂这层逻辑。一方面算法竞赛里 C 是大头高精度是基本功另一方面自己手写一遍会让你彻底明白计算机是怎么处理超出字长的数值的。面试时被问到“大数相加怎么实现”本质考的就是这个。1.2 数组模拟竖式的核心思想高精度最核心的两个设计决策用什么结构存数以及为什么低位放在数组前面。我用的是vectorint配合“低位在前”的存储方式。举个例子整数 12345 存进数组时顺序是[5, 4, 3, 2, 1]a[0]是个位a[1]是十位依此类推。这样设计的理由是加法和乘法产生的进位只会向高位扩散也就是数组的下标越来越大。如果采用“高位在前”的存储每次进位都得在数组头部插入元素时间复杂度会退化到 O(n)很痛苦。低位在前进位就变成了push_back操作摊还复杂度是 O(1)。有人可能会建议用字符数组或者string存储字符串的好处是不用处理输入时的大小写转换直接从0减到0就行。但字符串做中间运算时进位和借位要反复修改字符而且下标处经常出现需要转换成数字的麻烦。实战下来vectorint是最顺手的因为元素本身就是整数加减运算不用做 ASCII 转换而且后面做压位优化时一个元素可以直接存 0 到 9999 的大数用vectorint天然支持这种改造。还有一个细节高精度算法里数字 0 的表示要统一。我习惯用vectorint只存一个 0。减法、除法做完后如果结果全部为 0至少保留一个元素避免输出空字符串。这个边界问题在后面会反复出现。2. 基础运算的全实现字符串转数组、加法、减法2.1 从字符串到高精度数组的读写在做任何运算前先要解决两件事把输入字符串转成高精度数组把高精度数组转回字符串输出。这两步看着简单但不少 bug 都埋在这。下面这段代码我用了很久逻辑非常直接#include bits/stdc.h using namespace std; // 字符串 - 高精度数组低位在前 vectorint load(const string s) { vectorint a; for (int i s.size() - 1; i 0; --i) { a.push_back(s[i] - 0); } if (a.empty()) a.push_back(0); return a; } // 高精度数组 - 字符串去掉前导零 string to_string_big(const vectorint a) { int pos a.size() - 1; while (pos 0 a[pos] 0) --pos; // 至少保留一位 string res; for (int i pos; i 0; --i) { res.push_back(char(0 a[i])); } return res; }load里倒序遍历字符串把每个字符转成数字后再push_back这样低位天然就落在数组头部。to_string_big则从尾部高位开始找第一个非零元素如果全部是 0也保留最后一位所以输出永远是“0”不会输出空串。这里我要提醒一个容易出错的地方如果你从键盘读入的数字本身就带换行、空格或者是有符号的负号“-”上述load函数会因为无法处理符号而错乱。我的做法是读入整体字符串后先判一下首位是不是-如果是就单独记录符号标记再把剩余部分传入load。后面的比较、减法也已经考虑了符号维度但在基础模板里可以先只做非负数避免一上来就被负号搞晕。2.2 高精度加法进位处理与模板高精度加法是最容易上手的运算。原理就是竖式从低位到高位把两个数对应位相加加上来自低位的进位然后取个位作为当前结果位十位作为下一位的进位。循环结束后如果最高位还有进位再补一位。代码写出来非常紧凑// 高精度加法支持不同长度的 vector vectorint add(const vectorint a, const vectorint b) { vectorint c; int carry 0; int n max(a.size(), b.size()); for (int i 0; i n; i) { int sum carry; if (i (int)a.size()) sum a[i]; if (i (int)b.size()) sum b[i]; c.push_back(sum % 10); carry sum / 10; } if (carry) c.push_back(carry); return c; }这个模板有两个关键点。第一个是sum % 10和carry sum / 10这两个操作在十进制下相当于取个位和取十位。如果以后要做 16 进制高精度这里改成% 16和/ 16就行。第二个是max(a.size(), b.size())来确定循环次数避免两个数位数不同时漏掉较长那个数的剩余位。我在新手期犯过的最臭错误就是循环写成a.size()然后两个长度不等的数相加时高的位直接被丢掉了。调试小技巧单测就用最野的边界值。0 0必须输出 099 1必须输出 100 而不是 009999999 1必须输出 10000000。这几个用例过了加法基本就稳了。很多人在进位循环结束后忘了检查carry直接返回结果导致99100这是高精度加法里出现频率第一的错误。2.3 高精度减法比较大小、借位与符号处理减法比加法复杂一点原因在于借位和符号。竖式减法是从低位开始如果当前位的被减数小于减数就要向高位借 1。实现之前必须先判断谁大谁小因为负数的竖式计算规则不是简单地“符号留给外面内部始终用大的减小的”。先看比较函数。因为高精度数组是低位在前的比较大小的逻辑是先比长度长度不同则长度大的数更大长度相同再从最高位往低位逐个比较// 返回 true 如果 a b bool greater_big(const vectorint a, const vectorint b) { if (a.size() ! b.size()) return a.size() b.size(); for (int i a.size() - 1; i 0; --i) { if (a[i] ! b[i]) return a[i] b[i]; } return false; // 相等 } // 高精度减法前提 a b结果仍为非负数 vectorint sub(const vectorint a, const vectorint b) { vectorint c a; // 拷贝一份直接在拷贝上修改 int n a.size(); for (int i 0; i n; i) { int cur c[i]; if (i (int)b.size()) cur - b[i]; if (cur 0) { cur 10; if (i 1 n) c[i 1]--; // 向高位借 1 } c[i] cur; } // 去前导零 while (c.size() 1 c.back() 0) c.pop_back(); return c; }实际的带符号减法可以这样封装先比较a和b如果a b结果符号为正直接sub(a,b)否则结果为负就sub(b,a)后在输出层打负号。不要试图在sub内部做符号会让代码变得非常难读。减法里的一个坑借位后高位可能变成负数下一轮循环会继续借位链条会一直传递下去。我写的循环里第i位借位会影响c[i1]而i1在下一轮会被再次处理所以链条是通的。但如果循环顺序写反了从高位往低位处理就会出现“借位不知道借到哪里”的混乱。这个模块写过一次就别改了我后来所有高精度工具类都直接复用这两个基本函数。3. 乘除与进阶计算从乘法到除法再到阶乘幂3.1 高精度乘法双层循环与统一进位高精度乘法比加减法上了一个台阶因为它不再是单纯的一位对一位而是要处理两位之间的交叉乘积。原理还是竖式把a[i] * b[j]的结果累加到结果的第ij位。只不过这里我们不是每乘一步就立刻进位而是先把所有乘积都累加到位上最后统一处理进位。这样做的好处是减少进位次数避免大量无意义的取模操作。核心实现如下vectorint mul(const vectorint a, const vectorint b) { int n a.size(), m b.size(); vectorint c(n m, 0); for (int i 0; i n; i) { for (int j 0; j m; j) { c[i j] a[i] * b[j]; } } // 统一处理进位 int carry 0; for (int i 0; i n m; i) { int val c[i] carry; c[i] val % 10; carry val / 10; } // 结果长度可能虚高去掉前导零 while (c.size() 1 c.back() 0) c.pop_back(); return c; }注意细节a[i] * b[j]的结果在极端情况下可能达到 9 × 9 81累加多次后c[ij]可能超过 100。在逐位存储的版本里单个 c 的元素理论上最多是 81 × 长度长度大了就可能溢出int。不过如果长度不超过两千万位int 还是够的但在压位版本里中间结果会非常大所以我会用long long做统计或者分段处理。这里为了基础版清晰先用 int但在注释里标注这是需要注意的地方。还有一个性能点这个双层循环是 O(n*m)当两个数都是 10 万位时1e10 次乘法会慢到无法接受。所以高精度乘法后续通常要接 FFT 优化我放到后面专门说。3.2 高精度除法除以单精度与除以高精度高精度除法的实现通常分两类除以一个小整数单精度和除以另一个高精度大数大数除大数。除以单精度是最简单的一种因为除数小我们可以从最高位开始逐位处理每次把当前余数乘以 10 再加上当前位的数字然后除以除数得到商的一位剩下的作为余数带入下一位。这个逻辑和手算除法的试商过程一模一样。// 返回商同时通过引用的余数返回 vectorint div_mod_single(const vectorint a, int b, int remainder) { vectorint q(a.size(), 0); long long rem 0; for (int i a.size() - 1; i 0; --i) { rem rem * 10 a[i]; q[i] rem / b; rem % b; } while (q.size() 1 q.back() 0) q.pop_back(); remainder rem; return q; }这里我想提醒一个容易忽略的问题如果被除数本身为 0除完之后返回的q可能是空 vector 或者只有 0。上面的实现先把 q 初始化为a.size()大小所以不会为空然后去前导零也保证了至少保留一位。但如果a本身就是空 vector这在我早期的模板里可能出现就要在函数开头做兜底判断。至于大数除大数最自然的方式是模拟长除法但实现起来繁琐。更实用的是二分答案法对于a / b答案 q 必然落在 0 到 a 之间我们二分 q然后用高精度乘法判断q * b是否小于等于a。这种算法复杂度是 O(n^2 log V)n 是被除数位数V 是商的大小范围。当位数不多时它比手写长除法更不容易出错。二分法代码思路大概是这样vectorint div_big(const vectorint a, const vectorint b) { // 先处理特殊情况b 为 0 直接报错这里不演示这类错误分支 vectorint low(1, 0), high a; while (!greater_big(low, high)) { vectorint mid add(low, high); mid div_mod_single(mid, 2, ?); // 高精度除以2也可以直接用移位实现 if (greater_big(mul(mid, b), a)) { high sub(mid, vectorint(1,1)); // 不能在 mid 上直接改要先拷贝 } else { low add(mid, vectorint(1,1)); } // 需要做终止条件判断这里只是演示框架 } return low; }严格来说这个二分框架里终止条件的处理要非常小心尤其是 mid 和 low/high 相邻时要防止死循环。我的经验是直接在高精度运算基础上再封装一个带幂次的比较函数然后在循环结束时多验证一次。这种方案在笔试和面试讲思路时足够用但它不是最优实现如果你要在一个高负载项目里频繁使用大数除法我更推荐去用成熟的大数库比如 GMP。3.3 经典应用大数阶乘、快速幂与组合数有了加、减、乘、除这些原语之后就可以拼装出很多实用算法了。第一个经典应用是大数阶乘。比如计算100!用 long long 存会溢出用高精度乘法循环乘就行了vectorint factorial(int n) { vectorint res(1, 1); for (int i 2; i n; i) { vectorint factor; int t i; while (t 0) { factor.push_back(t % 10); t / 10; } res mul(res, factor); } return res; }每次把当前结果乘以下一个数由于 n 本身是普通整数所以构造因子时只要用普通除法拆位即可。时间复杂度是 O(n^2) 量级n 到 10000 时已经有点慢但 n 小于 1000 时体验很好。竞赛里经常用这种方法算组合数 C(n, k)因为阶乘取模的问题会牵扯到逆元而不取模的大组合数直接高精度乘除也能做只是要把所有中间结果都控制在高精度层面。第二个经典应用是快速幂配合高精度。像计算2^100这种直接循环乘 100 次就完事但如果要算2^100000就必须用快速幂。把指数拆成二进制每次把底数平方遇到当前位为 1 就把结果乘上底数。核心代码很短vectorint fast_pow(vectorint base, int exp) { vectorint result(1, 1); while (exp 0) { if (exp 1) result mul(result, base); base mul(base, base); exp 1; } return result; }这个版本的 base 可以是高精度exp 是普通整数。如果你要算的是高精度大数的幂指数本身也是大数那么快速幂依然适用但指数的二进制拆位就需要额外处理。我一般把指数转成 uint64_t如果指数位数超过 64 位就改用高精度存储并通过高精度除以 2 来遍历二进制位。这类进阶组合的通用价值在于高精度不是孤立的一两个函数而是一个可以叠加的组合框架。你先把加减乘除这些原语写稳阶乘、幂、组合数、取模就都成了简单拼装。我在实际比赛中最常用到的正好就是“高精度阶乘 高精度组合数 高精度取模”这套组合Gym 题里的 Extended Big Number 总结基本都是这套模板。4. 常见问题与性能优化实录4.1 五个高频 bug 现场高精度算法代码量不大但出错的频率出乎意料地高。根据我自己的排错记录和帮别人 review 的经验下面五种 bug 出现频率最高我直接整理成表方便你对照自查症状根因解法99 1 输出 00加法循环结束后没有把最后的进位 push_back在循环末尾判断if (carry) c.push_back(carry)100 - 99 输出 1 而不是 10 的前导零问题去除前导零时去掉了不该去的 0或者是减法借位后某一高位变成负数但未处理先去前导零再检查借位链是否完整123 * 456 输出结果位数不对多了一位 0乘法结果的初始长度设成了 nm且去掉前导零前忘了处理尾部多余的 0统一进位后再去前导零保留至少一位一个 5000 位的数除以 7输出为空除法的结果 vector 长度初始为 0前导零删除后整条链断了初始化 q 为被除数长度并保证至少保留一位在压位版本里输出 10000 时只输出 1输出时没有对当前元素做前导补零输出模板里对非最高位元素格式化 4 位不足补零这五个 case 基本就是我在代码 Review 时最常圈出的地方。尤其是第一个“加法忘进位”几乎每个从零手写高精度的人都要踩一次。我的建议是每一个函数写完都要做一个极小的测试脚本用十组以内的高覆盖用例跑一遍不要等整套模板写完再统一调那样定位 bug 的成本会高很多。4.2 压位优化让高精度运算更快逐位存储虽然直观直观但性能确实拉胯。数组长度大循环次数多vector 的内存访问也不够友好。如果要做大规模的阶乘、大数的乘法我建议上压位。压位的思路是把几个十进制位打包进一个int里比如万进制即每个元素存储 0 到 9999 的数字这样数组长度直接减小到原来的四分之一。进位处理时用的是 10000 而不是 10模运算和除法也相应地改成 10000。这样加、减、乘的循环次数都少了四倍而且内存占用也小了cache 友好度提升明显。压位版本的关键在于输入输出。输入时不能一个字符一个字符地存而是从字符串末尾每 4 个字符切一段转成整数后作为数组的一个元素存储。输出时除了最高位那段其余每段必须用setw(4) setfill(0)补零到 4 位否则像“10000”这种数字会输出成“1 0 0”这种错位形式。压位版 load 和输出示例vectorint load_base10000(const string s) { vectorint a; int len s.size(); for (int i len; i 0; i - 4) { int start max(0, i - 4); a.push_back(stoi(s.substr(start, i - start))); } if (a.empty()) a.push_back(0); return a; } string to_string_base10000(const vectorint a) { stringstream ss; ss a.back(); for (int i (int)a.size() - 2; i 0; --i) { ss setw(4) setfill(0) a[i]; } return ss.str(); }这里的stoi在字符串段是 4 位时不会溢出最大 9999安全。进位操作则把%10改成%10000把/10改成/10000。乘法中间结果用 long long 存因为a[i] * b[j]最大约 1e8累加多次可能接近亿级别但远小于 2^63-1所以用long long做累加是安全的。压位的增益我实测过计算 30000! 时逐位版本大约需要 4 到 5 秒压位到万进制后大概在 1 秒内。这个提升主要来自循环次数减少和内存减小。如果你的比赛环境内存限制较严格压位几乎是必然选择。4.3 选型思考什么时候用现成库有些读者可能会问“C 里不是有__int128也有 Boost 的 multiprecision还有 GMP为什么还要手写高精度”这个问题我认真想过答案是看场景。__int128是 GCC 和 Clang 的扩展能直接存储 128 位整数最大约 1.7e38比 long long 大得多运算速度也接近原生整型。但首先它不是标准 C换到 MSVC 环境下就不一定能用其次 128 位的范围依然有限一旦数值超过这个界限还是得回到高精度路线。所以我的习惯是中间结果确认不会超过 128 位的就优先用__int128性能最好一旦预估位数超过几百位直接上自己写的高精度模板。Boost.Multiprecision 的cpp_int和 GMP 都非常成熟功能强大GMP 甚至在某些大整数运算上比自己写的模板快几个数量级。但引入它们往往意味着依赖管理复杂度上升比赛环境不一定预装 GMP跨平台编译也更容易出问题。写业务代码时如果只是偶尔算一个大数用 Boost 是最省心的。但如果你想真正掌握算法原理或者需要在比赛中一个压缩包跑完所有代码手写高精度仍然是必备技能。我把常见方案整理成一张对照表方案表示范围性能可移植性适合场景long long19 位十进制极快极好常规计算、索引、计数__int12838 位十进制很快较依赖编译器中间结果超过 64 位但不太离谱时手写高精度任意位数一般可压位/FFT 优化极好算法竞赛、教学、无额外依赖环境Boost.Multiprecision任意位数较好有编译头依赖业务代码、工程实践GMP任意位数极快需要编译/链接库高性能大数计算、密码学等选型时不用纠结原则就是“性能够用、依赖可控、代码可维护”。手写高精度虽然性能一般但它最大的优势是零依赖在任意环境都能跑。4.4 扩展场景高精度的应用不止算法竞赛。金融系统里金额计算为了避免浮点误差常用十进制定点存储本质上就是一种高精度只是基数换成了分、厘这类单位加密算法里 RSA、ECC 都有大量的大数高频运算区块链、哈希碰撞检测也离不开大数处理。如果你以后在业务代码里碰到“这个数字用 int 存不下”“浮点精度无法接受”这类需求高精度模板就是你的底层工具箱。再延伸一步当高精度乘法遇到百万位级的输入时O(n²) 的手写竖式乘法会显得非常吃力这时候就该引入 FFT快速傅里叶变换或 NTT快速数论变换把乘法的复杂度降到 O(n log n)。我在前文提过的手写模板在竞赛够用但真做超大乘法时还是建议去了解一下 FFT 版本的实现。这又是独立的一大块知识体系但基础的高精度原语依然通用。最后再分享一个我自己的习惯高精度模板里的add、sub、mul、div_mod_single、greater_big这几个函数我会全部做成独立函数并且参数都用const vectorint绝不直接在原参数上修改。这样一个函数出问题时单测可以精确定位到某一环而不用在几十层调用之间来回追。加法和乘法之间可以组合出幂和阶乘减法与比较、除法之间可以组合出取模和整数除这套组合真的是算法比赛里最常碰的核心工具。写高精度最容易犯的错是急着把整套代码写出来再调试。我现在的流程是先写一个逐位版本跑通所有基础用例再去写压位版本压位版本出问题时用逐位版本去对拍几乎立刻就能看出是输出格式问题还是进位逻辑问题。这个“双版本对拍”的方法帮我省了不知道多少排查时间建议你也试试。
