搞编程竞赛这几年C的高精度模板是我重写次数最多的代码。原因很简单第一次写的时候只求跑出结果第二次写发现减法有边界bug第三次写才意识到乘法中间数组会溢出除法又是另一种麻烦。断断续续把这些坑踩完我才形成了一套自己真正用得顺手的大数加减乘除模板。这篇文章就把这套东西完整拆开从存储结构、进位借位原理到每段代码为什么这么写再到调试验证和压位优化一次性讲清楚。这套模板能解决什么问题一句话当数字超出long long范围约9.2×10^18时你需要用数组模拟竖式计算这就是高精度。适合谁看主要给准备算法竞赛的C选手以及需要在C/C环境里处理超长数值但又不想引第三方库的开发者。我会先把原理讲透再给完整可用的模板和避坑清单保证你读完能自己手搓一个出来。1. 高精度是什么为什么C选手必须亲手写一遍1.1 数据范围不够用的一天早晚会来先明确一个底线long long能表示的整数范围是-9223372036854775808到9223372036854775807大约正负9.2×10^18。这个范围在绝大多数工程场景里足够但在算法题里远远不够。斐波那契数列第100项已经超过1.7×10^20第1000项的位数超过200位第100000项更是有2万多位。阶乘、大数组合数、大数幂运算这些题目在竞赛里都高频出现答案动不动上百位用原生类型根本接不住。有人会问C不是有第三方大数库吗竞赛环境里通常不允许也不建议依赖。更多时候高精度不是单独考你一个点而是作为某个算法题的必要组件。比如矩阵快速幂求斐波那契时矩阵元素溢出就得用高精度状态压缩DP里计数范围超限也要用高精度。这时候会调库的人束手无策亲手写过模板的人反而能直接嵌进去用。这也是为什么ACM选手几乎人人都会维护一份自己的高精度模板。1.2 竖式运算高精度的底层原理高精度的核心思想其实特别朴素把小学学的竖式加减乘除用数组在计算机里重新实现一遍。无论数字多大先拆成一位一位或者几位一组存进数组然后从低位往高位逐位运算处理好进位和借位最后反向输出即可。只要内存够位数可以做到几万甚至几十万。举个例子计算123 456把两个数倒序存进数组a [3, 2, 1]b [6, 5, 4]从下标0开始逐位加369257145最后倒序输出[9, 7, 5] - 579如果某一位相加超过9比如3912那这一位保留2向高位进1。这就是竖式加法的全部逻辑。减法、乘法、除法也都是类似的模拟竖式思路。原理听着简单但真正写一套健壮的模板要处理进位的连续传播、借位的连锁反应、乘法结果的进位规整、除法试商的边界判断每一环都有坑。这也是我单独写一篇长文的原因真正理解这些细节比背模板重要得多。1.3 会背模板不等于会写模板我见过不少选手赛前背一份模板就上场遇到高精度题还是翻车。原因通常是模板是别人写的边界条件、前置假设、数据范围统统不清楚一旦题目有符号、有前导零、有除法取模模板就崩。高精度这种代码只有自己逐行写过、被bug折磨过才能知道它为什么长这样。所以我建议每个C竞赛选手都至少亲手实现一遍高精度加减乘除不要求一次写对但要理解每个细节的原理。这篇文章后半部分会给出完整模板但请把它当作校验答案而不是背诵材料。2. 数据结构选型数组、字符串与压位的权衡2.1 三种存储方式怎么选写高精度之前第一步是确定用什么容器存数字。常见方案有三种存储方案优点缺点适用场景固定长度数组 int a[N]写法直观内存固定最大位数写死扩展性差题目明确限制位数string字符串输入输出无需转换字符与数字转换繁琐运算慢简单场景/临时验证vectorint动态数组内存按需增长方便压位需要自己管理进位细节竞赛通用最佳选择我的默认选择一直是vectorint原因很实际高精度数的位数是动态的加法乘法会让结果变长vector能按需增长同时支持随机访问写起来和数组一样顺手。2.2 倒序存储的根因vector里存数字有两种排法正序d[0]是最高位和倒序d[0]是最低位。我强烈建议用倒序。原因有二进位和借位都从低位往高位流动。倒序存储时进位是往vector尾部加元素天然高效正序存储时高位进位需要在数组开头插入元素那是O(n)的移动代价在几万位的大数上就是灾难。乘法结果的定位也依赖下标。a[i]乘以b[j]的结果应该加到结果的ij位这个公式在倒序下非常自然正序反而容易算错位置。倒序唯一的代价是输出时要反向遍历但这只是循环方向的事性价比极高。2.3 压位到底压什么一个int能存到大约21亿只用来存0~9确实浪费。于是有人想让一个int存多位数。最常见的方案是万进制压位也就是一个int存0~9999相当于每4个十进制位压成一个int。压位的好处很直接同样表示一个1万位的大数一位一存需要1万个int万进制只要2500个。而在乘法这种O(n*m)复杂度的运算里位数缩小4倍内层循环次数也跟着缩小4倍实测压位版本比不压位快10倍以上。压位的代价是第一进位基数从10变成10000所有取模和除法操作要跟着改第二输出时除了最高组每组必须补0到4位否则会打印出1 23这种错误结果第三乘法中间值会变大可能需要用long long承接。这些细节会在第6部分详细展开。3. 核心实现加减乘除逐个拆解下面进入正题。我会先用绝对值运算的角度解释每个函数的写法因为加减乘除的核心就是处理非负整数的四则运算符号问题留到完整模板部分统一处理。3.1 加法进位是怎么流动的两个非负大整数相加逻辑就是从低位到高位逐位加每一位的结果是两数该位之和再加上上一位的进位结果位对10取模进位除以10。长度不一致时短的数高位补0即可。// 绝对值加法a b // 约定vector下标0是最低位数字倒序存储 vectorint addAbs(const vectorint a, const vectorint b) { int len max(a.size(), b.size()); // 两数中较长的位数 vectorint c(len 1, 0); // 多开一位用于承接最高位进位 for (int i 0; i len; i) { int ai i a.size() ? a[i] : 0; int bi i b.size() ? b[i] : 0; int s ai bi c[i]; // 本位的和 两个数位之和 低位进位 c[i] s % 10; c[i 1] s / 10; // 进位给下一位 } // 去掉前导0但至少保留1位 while (c.size() 1 c.back() 0) c.pop_back(); return c; }这里的细节是c[i]初值为0但在循环过程中可能先被上一位的进位写入这一位再加ai和bi逻辑上就是两数位之和加进位。注意len多开了一位因为991100这种场景最高位也会有进位。用999 1验证a倒序 [9,9,9]b倒序 [1]len3c开4位i0: s91010c[0]0c[1]1i1: s90110c[1]0c[2]1i2: s90110c[2]0c[3]1结果 c[0,0,0,1]倒序输出1000。正确3.2 减法借位比进位更考验细节减法比加法麻烦因为存在谁减谁的问题。如果允许结果为负就需要比较两个数的大小。先看绝对值减法前提是a b// 绝对值减法a - b调用前必须保证 a b vectorint subAbs(const vectorint a, const vectorint b) { vectorint c a; // 把被减数复制一份直接在副本上减 for (int i 0; i c.size(); i) { int bi i b.size() ? b[i] : 0; c[i] - bi; if (c[i] 0) { // 本位的数不够减向高位借1 c[i] 10; c[i 1]--; // 高位减1这个借位在下一轮循环继续处理 } } while (c.size() 1 c.back() 0) c.pop_back(); return c; }初学者最容易犯的错是把循环只写到b.size()以为减完b的每一位就结束了。这在1000 - 1时直接翻车i0时c[0]0-1-1借位后c[0]9c[1]变成-1如果循环就在这里停下c[1]的-1永远不会被处理结果就错了。正确的做法是循环扫到c.size()让借位像波浪一样一路传下去。我用1000 - 1手动跑一遍c初始为 [0,0,0,1]i0: c[0]0-1-1 - c[0]9, c[1]--i1: c[1]现在是-1bi0c[1]0 - c[1]9, c[2]--i2: c[2]现在是-1c[2]0 - c[2]9, c[3]--i3: c[3]当前是0bi0不减结果 [9,9,9,0] - 999。正确这里能看出一个经验写借位处理时循环范围一定要覆盖整个被减数而不是减数的长度。借位是无情的它可能跨过好几个0。3.3 乘法竖式相乘与统一进位高精度乘法分两种高精度乘低精度以及高精度乘高精度。竞赛里后者更常见。思路是a的第i位与b的第j位相乘结果累加到答案的ij位等全部乘完再统一做一次进位规整。// 绝对值乘法a * b vectorint mulAbs(const vectorint a, const vectorint b) { vectorint c(a.size() b.size(), 0); // 乘积位数不会超过两者位数之和 for (int i 0; i a.size(); i) { for (int j 0; j b.size(); j) { c[i j] a[i] * b[j]; } } // 统一处理进位从低位往高位逐位规整 for (int i 0; i 1 c.size(); i) { c[i 1] c[i] / 10; c[i] % 10; } while (c.size() 1 c.back() 0) c.pop_back(); return c; }这段代码有一个安全细节c[ij] a[i] * b[j]时c[ij]可能累加很多次。如果a和b的位数都是n那么单个c[ij]最多被累加约n次每次最大值是9*981所以中间值最多约81n。只要n不超过约2600万int就安全。竞赛里大数位数通常在几万以内int完全够用但如果你想写一个绝不怕溢出的版本可以把c的类型改成vector 进位时再把每位转回0~9代价只是内存翻倍。我自己的版本为了稳妥在关键地方会用long long中间变量。乘法的时间复杂度是O(n*m)是大数四则运算里最需要压位的环节。这也是为什么很多竞赛模板专门对乘法做压位优化后面会细讲。3.4 除法低精度除法与试商法高精度除法除法是四则运算里最特殊的它有两种常见形态。第一种高精度除以低精度也就是被除数很大但除数在int范围内。这种情况很好处理模拟手算除法从高位往低位逐位求商即可// 高精度除以低精度a / b例如 a 是 vectorintb 是 int vectorint divSmall(const vectorint a, int b, int rem) { vectorint c(a.size(), 0); long long r 0; // 余数用long long防止乘10后溢出 for (int i a.size() - 1; i 0; --i) { r r * 10 a[i]; c[i] r / b; r % b; } rem r; while (c.size() 1 c.back() 0) c.pop_back(); return c; }注意两个细节一是循环从最高位往下走因为除法竖式就是从高位开始商的二是r必须用long long因为r在乘10之后可能超过int范围比如余数接近10亿时。第二种高精度除以高精度这个复杂得多。我的实现思路是字符串试商法从被除数的高位开始逐位拉数字构造一个当前被除片段cur然后用9到1试商找到最大的k使得 k * b cur这一位就商k再把k*b从cur里减掉。之所以从9往下试是因为每一位商只可能是0~9而9次乘法比较是常数级别的开销写起来最不容易错。先需要一个字符串比较函数和一个字符串减法以及一个高精度字符串乘以一位数的小函数// 去掉字符串前导0但保底一位 string normStr(string s) { int p 0; while (p 1 s.size() s[p] 0) p; return s.substr(p); } // 字符串数字比较ab返回-1相等返回0ab返回1 int cmpStr(const string a, const string b) { string sa normStr(a), sb normStr(b); if (sa.size() ! sb.size()) return sa.size() sb.size() ? -1 : 1; if (sa sb) return 0; return sa sb ? -1 : 1; } // 字符串减法前提 a b string subStr(const string a, const string b) { string ra(a.rbegin(), a.rend()), rb(b.rbegin(), b.rend()); string res; int carry 0; for (size_t i 0; i ra.size(); i) { int v (ra[i] - 0) - carry - (i rb.size() ? (rb[i] - 0) : 0); if (v 0) { v 10; carry 1; } else carry 0; res.push_back(char(0 v)); } while (res.size() 1 res.back() 0) res.pop_back(); reverse(res.begin(), res.end()); return res; } // 字符串数字乘以一位数 string mulSmall(const string a, int k) { if (k 0) return 0; string res; int carry 0; for (int i a.size() - 1; i 0; --i) { int v (a[i] - 0) * k carry; res.push_back(char(0 v % 10)); carry v / 10; } if (carry) res.push_back(char(0 carry)); reverse(res.begin(), res.end()); return res; } // 高精度除法a / bq为商rem为余数 string divStr(const string a, const string b, string rem) { if (b 0) return 0; // 除数为0这里按约定返回0实际应报错 string q, cur; for (char ch : a) { cur.push_back(ch); cur normStr(cur); if (cmpStr(cur, b) 0) { q.push_back(0); // 当前不够除商0 continue; } int k 9; for (; k 1; --k) { string tmp mulSmall(b, k); if (cmpStr(tmp, cur) 0) break; } q.push_back(char(0 k)); cur subStr(cur, mulSmall(b, k)); cur normStr(cur); } rem cur.empty() ? 0 : cur; return normStr(q.empty() ? 0 : q); }这套除法用字符串做接口是因为从高位逐位拉数字天然对应字符串下标而内部用到的比较、乘法和减法本质还是高精度运算。如果你希望全程用vector实现除法思路完全一样只是要额外维护一个当前片段的vector并处理每次拉数字导致的整体增长。字符串方案更直观适合绝大多数竞赛场景。试商从9开始向下逐个尝试每次最多9次乘法比较。虽然常数不小但每一位商最多9次整体复杂度仍可控而且这种写法避免了很多复杂的高精度倍增逻辑出bug的概率低得多。4. 完整模板从绝对值运算到带符号类4.1 输入输出与符号处理第3部分讲的全都是绝对值运算也就是默认两个数都是非负的。但竞赛题里的高精度数经常带负号所以完整模板必须处理符号。符号处理规则其实很简单加法同号则绝对值相加符号不变异号则取绝对值大的那个数的符号做绝对值相减。减法转换成一元负号 加法即 a-b a (-b)。乘法结果符号由两个数的符号异或决定同号为正、异号为负绝对值相乘。除法与乘法同理符号异或绝对值相除。这样可以避免为每一种运算都写一堆分支只需在运算符重载层面统一处理。输入时要注意负号和前导零字符串里可能有或-也可能有00123这种前导零。构造BigInt内部时先去符号再删前导零最后倒序存入vector。4.2 模板代码分块解析下面给出完整模板的关键代码块。我把类定义、构造与输出、运算函数分别列出使用时按顺序拼装即可。#include bits/stdc.h using namespace std; struct BigInt { vectorint d; // 倒序存储d[0]是最低位 bool neg; // 是否为负数 BigInt() : d(1, 0), neg(false) {} // 从字符串构造 BigInt(const string s) { int pos 0; neg false; if (pos s.size() (s[pos] || s[pos] -)) { neg (s[pos] -); pos; } while (pos s.size() s[pos] 0) pos; // 去前导0 string t s.substr(pos); if (t.empty()) t 0; d.clear(); for (int i t.size() - 1; i 0; --i) d.push_back(t[i] - 0); if (d.size() 1 d[0] 0) neg false; // 0没有负号 } // 转字符串输出 string toString() const { string s; if (neg) s.push_back(-); for (int i d.size() - 1; i 0; --i) s.push_back(char(0 d[i])); return s; } };绝对值比较与加减乘其实就是第3部分的函数只需要做一点封装。我建议把所有绝对值运算函数定义成普通的函数比如上面的addAbs、subAbs、mulAbs放在类外面类里面再做符号封装。这样拆开的好处是如果你只需要非负高精度直接调用绝对值函数就行不需要创建对象。符号封装示例如下BigInt operator(const BigInt x, const BigInt y) { BigInt res; if (x.neg y.neg) { res.d addAbs(x.d, y.d); res.neg x.neg; } else { int cmp cmpAbs(x.d, y.d); // 比较绝对值大小 if (cmp 0) { res.d subAbs(x.d, y.d); res.neg x.neg; } else { res.d subAbs(y.d, x.d); res.neg y.neg; } } if (res.d.size() 1 res.d[0] 0) res.neg false; return res; } BigInt operator-(const BigInt x, const BigInt y) { BigInt ny y; ny.neg !ny.neg; // a-b a(-b) return x ny; } BigInt operator*(const BigInt x, const BigInt y) { BigInt res; res.d mulAbs(x.d, y.d); res.neg x.neg ^ y.neg; if (res.d.size() 1 res.d[0] 0) res.neg false; return res; }除法部分因为divStr用字符串接口所以类里需要做个桥接把x.toString()和y.toString()传给divStr商和余数再各自构造BigInt返回。取模运算则直接取余数。BigInt operator/(const BigInt x, const BigInt y) { string rem; string q divStr(x.toString(), y.toString(), rem); BigInt res(q); res.neg x.neg ^ y.neg; if (res.d.size() 1 res.d[0] 0) res.neg false; return res; } BigInt operator%(const BigInt x, const BigInt y) { string rem; divStr(x.toString(), y.toString(), rem); BigInt res(rem); res.neg false; // 取模结果一般保持非负按题目需要调整 return res; }这个模板整体不算短但结构很清晰一套绝对值运算函数一套class包装和符号处理外加除法字符串桥接。加上注释大概200行作为竞赛板子完全能接受。4.3 一个完整的调用示例为了让你看得更直观这里给一个简单用例计算两个大数的四则运算int main() { string a, b; cin a b; BigInt x(a), y(b); cout 加法: (x y).toString() \n; cout 减法: (x - y).toString() \n; cout 乘法: (x * y).toString() \n; BigInt rem(0); BigInt q x / y; BigInt r x % y; cout 除法商: q.toString() \n; cout 余数: r.toString() \n; return 0; }注意除法要求y不为0这一点在正式提交前一定要想清楚题目数据通常不会给除零但自己的模板要留好防御性返回。5. 测试、调试与避坑实录5.1 边界用例与随机数验证高精度模板最大的陷阱是边界值。我每次写完都会先跑几组特定用例999 1验证进位连续传播1000 - 1验证借位跨零传播123 * 456验证乘法结果1000000 / 9验证除法商和余数0 0、0 * 999、5 - 5验证前导零和零的处理这些用例能覆盖大多数基础错误。除此之外强烈建议用随机数标准答案做交叉验证本地用Python脚本生成随机大数把输入喂给C程序逐行对比输出。Python的大整数就是天然标准答案。这种方法看起来土效率却极高能一次性抓出几十种隐藏边界问题。我个人的习惯是写一个测试脚本循环生成1000组随机数据每组都对比C模板与Python int的计算结果。只要有一次不一致就缩小范围定位到具体用例。这个流程跑下来模板的正确性基本就稳了。5.2 常见问题速查表现象原因解决输出前多出一串0运算后没去前导零每个函数返回前统一执行去前导零减法结果错加法乘法正常借位循环范围只到b.size()没处理高位借位循环扫到c.size()乘法在位数很大的时候崩溃中间数组int溢出中间vector改用long long进位再转int除法商少一位或者余数不对试商前没清理cur的前导0每轮拉下新位后先normStr再比较字符串转vector反了忘了倒序存储约定统一约定从字符串末尾往前存带符号输入结果符号错构造BigInt时没处理前导0和负号构造时先摘符号删前导01000 - 1返回9990借位传播没跨过中间的0循环范围必须覆盖被减数全体这张表里的很多坑我自己都踩过。尤其是减法借位和字符串前导零这两条几乎每个初学者都会遇到值得反复提醒。5.3 一次减法WA的排查记录去年在某场线上练习赛一道大数减法题反复WA。我第一反应是模板的subAbs写错了翻来覆去看了半小时没发现问题。后来把输入数据原样打印出来才发现数据里居然有前导零比如0000123 - 0000001。我的BigInt构造里确实删了前导零但比较函数用的是未经规范的字符串导致compare判断失误符号选反。那次之后我给自己定了一条规矩任何读入的字符串在进入BigInt之前必须先统一规范——去符号、删前导零、再转内部数组。比较函数也只对规范后的字符串/数组负责绝不直接拿原始字符串比较。这条规矩后来帮我避开了一大类输入脏数据导致的bug。6. 性能优化从能用跑到跑得快6.1 万进制压位怎么做如果题目把高精度推到极限比如位数达到10万、100万一位一存的内层循环必然超时。万进制压位是性价比最高的优化手段具体做法读入字符串后从低位开始按4位一组切分如123456789 - [6789, 2345, 1]进位基数从10改成10000加法里s % 10000留在本位s / 10000进到高位乘法里c[ij] a[i] * b[j]的中间值最大约9999*9999必须用long long承接输出时反向遍历除了最高组其余每组用printf(%04d)补0我实测过一个10000位乘以10000位的乘法一位一存版本耗时约0.8秒万进制压位后降到约0.06秒差距超过10倍。位数越大差距越恐怖。压位版本的核心函数写法如下// 万进制压位乘法a、b中每个int存0~9999 vectorint mulBase10000(const vectorint a, const vectorint b) { vectorlong long c(a.size() b.size(), 0); for (size_t i 0; i a.size(); i) for (size_t j 0; j b.size(); j) c[i j] 1LL * a[i] * b[j]; vectorint res(c.size()); long long carry 0; for (size_t i 0; i c.size(); i) { c[i] carry; res[i] c[i] % 10000; carry c[i] / 10000; } while (res.size() 1 res.back() 0) res.pop_back(); return res; }这段代码在进位处理上做了优化把进位和累加结果放一起从低位向高位扫一遍完成规整。注意c用long long因为单个c[ij]可能被累加很多次加上进位后很容易超过int范围。6.2 传参方式与内存复用模板在性能上的另一个关键点是参数传递。所有绝对值运算函数都应该用const引用接收参数避免拷贝整个vectorvectorint addAbs(const vectorint a, const vectorint b);返回值按值返回是必要的但要留意临时对象的分配开销。如果在一个循环里反复调用乘法vector内部会频繁分配内存。我通常会对高频使用的函数做一点优化在函数内部先reserve出足够的容量减少扩容次数。乘法的目标数组长度是a.size()b.size()明确知道大小直接初始化到位即可。除法里反复调用mulSmall和subStr会创建大量临时字符串。虽然字符串方案直观但性能敏感时建议换成vector方案至少把cur维护成vector避免字符串拷贝。如果你只在比赛里偶尔用除法字符串方案完全够用。6.3 什么时候根本不需要高精度最后泼一盆冷水不是所有大数题都需要高精度。如果题目写着输出答案对10^97取模那通常意味着答案本身可以无限大但我们只需要结果对模数取余。这时全程用long long做快速幂、取模运算即可完全用不上高精度模板。判断标准很简单题目是否明确要求输出完整的大数。只有明确要求输出真实数值时才把BigInt掏出来。很多新人看到大数两个字就慌了其实是判断错了考点。先读清楚题再决定要不要上高精度这是省时省力的第一步。回到模板本身。说实话高精度是我认为最值得亲手写一遍的模板类型。它代码量不大但原理几乎覆盖了竞赛里所有数字边界问题进位、借位、溢出、前导零、符号、除零。写一遍调试一遍再看一遍别人的写法基本就忘不掉了。我每次打比赛前都会顺手把这几个函数默写一遍过程通常不超过十分钟——因为理解了竖式原理之后这些代码已经是肌肉记忆而不是死记硬背。最后再分享一个小技巧。我给模板里的每个函数开头都加了一行注释写清前置条件。比如 subAbs 的函数注释是前提a b。这个习惯救了我无数次调试的时候只要扫一遍注释就能快速排除是不是我调用方式错了的可能。模板会伴随你很长一段时间注释写清楚其实是给自己节省时间。希望这份整理能让你少踩几个我踩过的坑一次写出能安稳退役的高精度模板。