搞编程竞赛这几年,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开始逐位加:3+6=9,2+5=7,1+4=5
- 最后倒序输出:[9, 7, 5] -> 579
如果某一位相加超过9,比如3+9=12,那这一位保留2,向高位进1。这就是竖式加法的全部逻辑。减法、乘法、除法也都是类似的"模拟竖式"思路。
原理听着简单,但真正写一套健壮的模板,要处理进位的连续传播、借位的连锁反应、乘法结果的进位规整、除法试商的边界判断,每一环都有坑。这也是我单独写一篇长文的原因:真正理解这些细节,比背模板重要得多。
1.3 会背模板不等于会写模板
我见过不少选手,赛前背一份模板就上场,遇到高精度题还是翻车。原因通常是:模板是别人写的,边界条件、前置假设、数据范围统统不清楚,一旦题目有符号、有前导零、有除法取模,模板就崩。高精度这种代码,只有自己逐行写过、被bug折磨过,才能知道它为什么长这样。
所以我建议每个C++竞赛选手都至少亲手实现一遍高精度加减乘除,不要求一次写对,但要理解每个细节的原理。这篇文章后半部分会给出完整模板,但请把它当作校验答案,而不是背诵材料。
2. 数据结构选型:数组、字符串与压位的权衡
2.1 三种存储方式怎么选
写高精度之前,第一步是确定用什么容器存数字。常见方案有三种:
| 存储方案 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 固定长度数组 int a[N] | 写法直观,内存固定 | 最大位数写死,扩展性差 | 题目明确限制位数 |
| string字符串 | 输入输出无需转换 | 字符与数字转换繁琐,运算慢 | 简单场景/临时验证 |
| vector<int>动态数组 | 内存按需增长,方便压位 | 需要自己管理进位细节 | 竞赛通用最佳选择 |
我的默认选择一直是vector<int>,原因很实际:高精度数的位数是动态的,加法乘法会让结果变长,vector能按需增长;同时支持随机访问,写起来和数组一样顺手。
2.2 倒序存储的根因
vector里存数字,有两种排法:正序(d[0]是最高位)和倒序(d[0]是最低位)。我强烈建议用倒序。
原因有二:
- 进位和借位都从低位往高位流动。倒序存储时,进位是往vector尾部加元素,天然高效;正序存储时,高位进位需要在数组开头插入元素,那是O(n)的移动代价,在几万位的大数上就是灾难。
- 乘法结果的定位也依赖下标。a[i]乘以b[j]的结果应该加到结果的i+j位,这个公式在倒序下非常自然,正序反而容易算错位置。
倒序唯一的代价是输出时要反向遍历,但这只是循环方向的事,性价比极高。
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是最低位,数字倒序存储 vector<int> addAbs(const vector<int>& a, const vector<int>& b) { int len = max(a.size(), b.size()); // 两数中较长的位数 vector<int> 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多开了一位,因为99+1=100这种场景,最高位也会有进位。
用999 + 1验证:
- a倒序 [9,9,9],b倒序 [1],len=3,c开4位
- i=0: s=9+1+0=10,c[0]=0,c[1]=1
- i=1: s=9+0+1=10,c[1]=0,c[2]=1
- i=2: s=9+0+1=10,c[2]=0,c[3]=1
- 结果 c=[0,0,0,1],倒序输出1000。正确
3.2 减法:借位比进位更考验细节
减法比加法麻烦,因为存在谁减谁的问题。如果允许结果为负,就需要比较两个数的大小。先看绝对值减法,前提是a >= b:
// 绝对值减法:a - b,调用前必须保证 a >= b vector<int> subAbs(const vector<int>& a, const vector<int>& b) { vector<int> 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时直接翻车:i=0时c[0]=0-1=-1,借位后c[0]=9,c[1]变成-1;如果循环就在这里停下,c[1]的-1永远不会被处理,结果就错了。
正确的做法是循环扫到c.size(),让借位像波浪一样一路传下去。我用1000 - 1手动跑一遍:
- c初始为 [0,0,0,1]
- i=0: c[0]=0-1=-1 -> c[0]=9, c[1]--
- i=1: c[1]现在是-1,bi=0,c[1]<0 -> c[1]=9, c[2]--
- i=2: c[2]现在是-1,c[2]<0 -> c[2]=9, c[3]--
- i=3: c[3]当前是0,bi=0,不减
- 结果 [9,9,9,0] -> 999。正确
这里能看出一个经验:写借位处理时,循环范围一定要覆盖整个被减数,而不是减数的长度。借位是无情的,它可能跨过好几个0。
3.3 乘法:竖式相乘与统一进位
高精度乘法分两种:高精度乘低精度,以及高精度乘高精度。竞赛里后者更常见。思路是:a的第i位与b的第j位相乘,结果累加到答案的i+j位,等全部乘完,再统一做一次进位规整。
// 绝对值乘法:a * b vector<int> mulAbs(const vector<int>& a, const vector<int>& b) { vector<int> 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[i+j] += a[i] * b[j]时,c[i+j]可能累加很多次。如果a和b的位数都是n,那么单个c[i+j]最多被累加约n次,每次最大值是9*9=81,所以中间值最多约81n。只要n不超过约2600万,int就安全。竞赛里大数位数通常在几万以内,int完全够用;但如果你想写一个绝不怕溢出的版本,可以把c的类型改成vector ,进位时再把每位转回0~9,代价只是内存翻倍。我自己的版本为了稳妥,在关键地方会用long long中间变量。
乘法的时间复杂度是O(n*m),是大数四则运算里最需要压位的环节。这也是为什么很多竞赛模板专门对乘法做压位优化,后面会细讲。
3.4 除法:低精度除法与试商法高精度除法
除法是四则运算里最特殊的,它有两种常见形态。
第一种:高精度除以低精度
也就是被除数很大,但除数在int范围内。这种情况很好处理,模拟手算除法从高位往低位逐位求商即可:
// 高精度除以低精度:a / b,例如 a 是 vector<int>,b 是 int vector<int> divSmall(const vector<int>& a, int b, int& rem) { vector<int> 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); } // 字符串数字比较:a<b返回-1,相等返回0,a>b返回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 / b,q为商,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 { vector<int> 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和负号 | 构造时先摘符号,删前导0 |
| 1000 - 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[i+j] += a[i] * b[j]的中间值最大约9999*9999,必须用long long承接
- 输出时反向遍历,除了最高组,其余每组用printf("%04d")补0
我实测过:一个10000位乘以10000位的乘法,一位一存版本耗时约0.8秒,万进制压位后降到约0.06秒,差距超过10倍。位数越大,差距越恐怖。
压位版本的核心函数写法如下:
// 万进制压位乘法:a、b中每个int存0~9999 vector<int> mulBase10000(const vector<int>& a, const vector<int>& b) { vector<long 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]; vector<int> 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[i+j]可能被累加很多次,加上进位后很容易超过int范围。
6.2 传参方式与内存复用
模板在性能上的另一个关键点是参数传递。所有绝对值运算函数都应该用const引用接收参数,避免拷贝整个vector:
vector<int> addAbs(const vector<int>& a, const vector<int>& b);返回值按值返回是必要的,但要留意临时对象的分配开销。如果在一个循环里反复调用乘法,vector内部会频繁分配内存。我通常会对高频使用的函数做一点优化:在函数内部先reserve出足够的容量,减少扩容次数。乘法的目标数组长度是a.size()+b.size(),明确知道大小,直接初始化到位即可。
除法里反复调用mulSmall和subStr,会创建大量临时字符串。虽然字符串方案直观,但性能敏感时建议换成vector方案,至少把cur维护成vector避免字符串拷贝。如果你只在比赛里偶尔用除法,字符串方案完全够用。
6.3 什么时候根本不需要高精度
最后泼一盆冷水:不是所有"大数"题都需要高精度。如果题目写着"输出答案对10^9+7取模",那通常意味着答案本身可以无限大,但我们只需要结果对模数取余。这时全程用long long做快速幂、取模运算即可,完全用不上高精度模板。
判断标准很简单:题目是否明确要求输出完整的大数。只有明确要求输出真实数值时,才把BigInt掏出来。很多新人看到"大数"两个字就慌了,其实是判断错了考点。先读清楚题,再决定要不要上高精度,这是省时省力的第一步。
回到模板本身。说实话,高精度是我认为最值得"亲手写一遍"的模板类型。它代码量不大,但原理几乎覆盖了竞赛里所有数字边界问题:进位、借位、溢出、前导零、符号、除零。写一遍,调试一遍,再看一遍别人的写法,基本就忘不掉了。我每次打比赛前都会顺手把这几个函数默写一遍,过程通常不超过十分钟——因为理解了竖式原理之后,这些代码已经是肌肉记忆而不是死记硬背。
最后再分享一个小技巧。我给模板里的每个函数开头都加了一行注释,写清前置条件。比如 subAbs 的函数注释是"前提:a >= b"。这个习惯救了我无数次:调试的时候只要扫一遍注释,就能快速排除"是不是我调用方式错了"的可能。模板会伴随你很长一段时间,注释写清楚,其实是给自己节省时间。希望这份整理能让你少踩几个我踩过的坑,一次写出能安稳退役的高精度模板。