第 37 章 大数计算——高精度运算
🏗️ 前情回顾：你学过
int（约 ±2×10⁹）、long long（约 ±9×10¹⁸），以为这就够大了？但在一些题目中，你需要计算 100 的阶乘、2 的 100 次方、或者两个 100 位的整数相乘——这些结果远远超出long long的范围。这时候你不能依赖 CPU 原生的加减乘除，而要用字符串 + 逐位运算来模拟手工计算。
🎯 本章目标
学完这一章，你能：
- 理解高精度运算的本质：用字符串/数组模拟竖式计算
- 实现高精度加法（逐位加 + 进位）
- 实现高精度减法（借位 + 符号处理）
- 实现高精度乘法（高精 × 单精、高精 × 高精）
- 实现高精度除法（高精 ÷ 单精）
- 处理前导零、比较大小、压位优化等细节
📖 故事引入
你同学说："我能在 5 秒钟内算出 123456789 × 987654321。"你正要拿计算器，他却说："别急，我要精确到个位，不是科学计数法。"你看了看 long long 的极限……最大也就是 9 后面 18 位，这两个 9 位数相乘结果有 17~18 位，勉强能装下。但如果他说的是"两个 50 位数相乘"呢？计算器也显示不全。
这时候你唯一的办法就是——像小学生一样列竖式！
你拿出一张纸，把两个大数字逐位对齐，从个位开始一位一位乘、一位一位加、逐位进位。代码要做的就是把这张纸上的过程用数组模拟出来。CPU 不认识"100 位的整数"，但它认识"100 个 0~9 的数字"。用数组/字符串存储每一位，手动实现加减乘除——这就是高精度运算。
🧱 知识讲解
37.1 高精度存储：用字符串/数组表示大数
高精度运算的第一步是存储。通常采用两种方式：
方式一：字符串（便于输入输出）
string s = "12345678901234567890";方式二：整型数组（便于计算）
int a[1005]; // a[0] 存个位，a[1] 存十位……
int len; // 数字长度📦 类比：字符串是"展示层"——给人看的；整型数组是"计算层"——给 CPU 算的。输入时用字符串读入，然后转换成数组（通常是倒序存储：下标 0 存个位，下标 1 存十位……这样进位时往高处加更方便）。
字符串转数组（倒序存储）：
// 将字符串 s 转换为整型数组 a（个位在 a[1]，方便与"下标 0 不用"对齐）
void strToArr(string s, int a[]) {
int len = s.size();
a[0] = len; // a[0] 存长度（常用约定）
for (int i = 0; i < len; i++) {
a[len - i] = s[i] - '0'; // 倒序：s[0]（最高位）→ a[len]（最高位）
}
}⚠️ 有些教材把
a[0]用作长度，有些用独立变量len。二者皆可，但要保持统一。本书示例用独立len变量，a[1]~a[len]存数字（个位到最高位）。
37.2 高精度加法
和手工列竖式一模一样：从个位（下标 1）开始逐位相加，逢 10 进 1。
// a + b = c，返回 c 的长度
int add(int a[], int la, int b[], int lb, int c[]) {
int lc = max(la, lb);
int carry = 0; // 进位
for (int i = 1; i <= lc; i++) {
int ai = (i <= la) ? a[i] : 0;
int bi = (i <= lb) ? b[i] : 0;
c[i] = ai + bi + carry;
carry = c[i] / 10; // 计算进位
c[i] %= 10; // 当前位只保留个位
}
if (carry > 0) { // 最高位还有进位
c[++lc] = carry;
}
return lc;
}模拟 123 + 89：
i=1: 3+9+0=12 → c[1]=2, carry=1
i=2: 2+8+1=11 → c[2]=1, carry=1
i=3: 1+0+1=2 → c[3]=2, carry=0
结果：21237.3 高精度减法
减法比加法多一个前提：先判断大小，确保大减小。如果 a < b，就交换并用负号标记结果。
// 比较 a 和 b 的大小（假设长度分别为 la, lb）
int cmp(int a[], int la, int b[], int lb) {
if (la != lb) return la - lb; // 长度不同，长的更大
for (int i = la; i >= 1; i--) // 长度相同，从高位比到低位
if (a[i] != b[i])
return a[i] - b[i];
return 0; // 相等
}
// a - b = c（保证 a ≥ b），返回 c 的长度
int sub(int a[], int la, int b[], int lb, int c[]) {
int lc = la;
int borrow = 0; // 借位
for (int i = 1; i <= lc; i++) {
int ai = a[i] - borrow;
int bi = (i <= lb) ? b[i] : 0;
if (ai < bi) {
ai += 10;
borrow = 1;
} else {
borrow = 0;
}
c[i] = ai - bi;
}
// 去除前导零
while (lc > 1 && c[lc] == 0) lc--;
return lc;
}📦 类比：减法就像借钱——当前位不够减时，向高位"借 1 当 10"。高位被借后自己少了 1，所以需要标记
borrow = 1。
37.4 高精度乘法
高精 × 单精
一个大数乘以一个普通整数（能用 int 存下的）：
// a × b = c（b 是普通 int），返回 c 的长度
int mulSingle(int a[], int la, int b, int c[]) {
int lc = la;
long long carry = 0; // 进位可能很大，用 long long
for (int i = 1; i <= lc; i++) {
carry += (long long)a[i] * b;
c[i] = carry % 10;
carry /= 10;
}
while (carry > 0) {
c[++lc] = carry % 10;
carry /= 10;
}
return lc;
}高精 × 高精
两个大数相乘——经典竖式：a 的每一位和 b 的每一位相乘，结果累加到 c[i+j-1]，最后统一处理进位。
int mul(int a[], int la, int b[], int lb, int c[]) {
// 初始化 c 为 0
memset(c, 0, sizeof(int) * (la + lb + 5));
int lc = la + lb; // 乘积最大长度为 la+lb
for (int i = 1; i <= la; i++) {
for (int j = 1; j <= lb; j++) {
c[i + j - 1] += a[i] * b[j]; // 先全部累加，最后统一进位
}
}
// 统一处理进位
for (int i = 1; i <= lc; i++) {
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
// 去除前导零
while (lc > 1 && c[lc] == 0) lc--;
return lc;
}为什么要"先累加再统一进位"？因为 a[i] × b[j] 贡献到 c[i+j-1] 位置，而同一位可能收到来自不同 (i,j) 对的贡献。如果每步都进位，可能导致处理混乱。先全加完再一次性进位，代码清晰且不容易出错。
复杂度：O(la × lb)，两个 n 位数相乘就是 O(n²)。有更快的算法（如 FFT），但 O(n²) 足以应对竞赛中 n ≤ 10⁴ 的高精度乘法。
37.5 高精度除法（高精 ÷ 单精）
// a ÷ b = q（商），返回 q 的长度；余数存到 remainder
int divSingle(int a[], int la, int b, int q[], int &remainder) {
long long r = 0; // 当前余数
int lq = 0;
// 从高位到低位
for (int i = la; i >= 1; i--) {
r = r * 10 + a[i];
q[i] = r / b; // 商的第 i 位（注意：高位 q[la] 可能为 0）
r %= b;
}
remainder = r;
// 确定商的长度（去除前导零）
lq = la;
while (lq > 1 && q[lq] == 0) lq--;
return lq;
}⚠️ 除法是从高位到低位进行，与加减乘的"从低位到高位"方向相反——这和手工竖式除法一致。
高精 ÷ 高精 比较繁琐（需要多次减法模拟），竞赛中不常出现。原理是用"试商"——不断从被除数中减去除数的倍数。如果你感兴趣，可以自行搜索"高精度除法 高精除高精"。
37.6 前导零与输出
高精度计算完的结果可能带有前导零（比如 000123），输出前要去掉：
void print(int a[], int len) {
for (int i = len; i >= 1; i--) {
cout << a[i];
}
// 如果 len 已经是去除前导零之后的长度，直接倒序输出即可
}37.7 压位技巧（进阶）
每次只存 0~9 的一位数效率不太高。可以把多位"打包"存到一个数组元素中——比如每个元素存 4 位（0~9999），这样 100 位的大数只需要 25 个数组元素，运算速度提升约 4 倍。
const int BASE = 10000; // 每个元素存 4 位
const int WIDTH = 4; // 输出时补齐 4 位
// 进位：c[i] % BASE；进位：c[i] / BASE💡 压位技巧适合进阶使用。初学时建议先掌握普通高精度（每元素存 1 位），理解清楚后再加上压位。
✋ 动手试试
试试 1：写高精度加法，输入两个不超过 100 位的正整数，输出它们的和。
试试 2：写高精度乘法（高精 × 单精），输入一个大数和一个小整数，输出乘积。
试试 3：改进加法程序，支持"多个大数连加"——输入 n 和大数列表，输出总和。
⚠️ 容易犯的错
错 1：存储方向搞混
❌ a[1] 存最高位、a[len] 存个位——这样进位时下标越来越小，很别扭。
✅ 通常约定 a[1] 存个位，a[len] 存最高位。进位时往 a[len+1] 扩展，逻辑自然。
错 2：减法忘记比较大小
❌ 直接用 sub(a, b, c)，没有检查 a 是否 ≥ b。如果 a < b，结果是错误的"补数"。
✅ 先 cmp 比较，若 a < b 则交换并输出负号。
错 3：乘法中进位溢出
❌ int carry = 0; ... carry += a[i] * b; ——a[i] × b 可能达到 9×10⁹，int 溢出。
✅ 用 long long carry 接收累加值。
错 4：输出时忘记去除前导零
❌ 减法结果 100 - 99 = 1，但数组里是 [1, 0, 0]（长度 3），按 len=3 输出会变成 001。
✅ 减法/除法后要 while (lc > 1 && c[lc] == 0) lc--;
📝 练习
基础题
1. 选择题
（1）高精度运算中用数组存储大数，通常约定：
A. a[0] 存个位 B. a[1] 存个位 C. a[len] 存个位 D. 顺序无所谓
（2）两个 n 位数相乘，结果最多有几位？
A. n B. n+1 C. 2n D. 2n+1
（3）高精度除法与加减乘的不同在于：
A. 用减法实现 B. 从高位到低位处理 C. 不需要进位 D. 不需要借位
2. 填空题
（1）高精度加法中，进位 carry 的计算公式是 carry = c[i] ___ 10。
（2）高精度减法中，借位的核心操作是"不够减时向高位借 1 当 ____"。
（3）高精 × 高精中，a[i] × b[j] 结果贡献到 c[___] 位置。
提高题
3. 编程题 — A+B Problem（高精度版）
输入两个不超过 200 位的正整数，输出它们的和。
4. 编程题 — 阶乘之和
输入 n（1 ≤ n ≤ 50），输出 1! + 2! + ... + n! 的精确值。（用高精 × 单精 + 高精加）
挑战题
5. 编程题 — 2 的 n 次方
输入 n（0 ≤ n ≤ 500），输出 2ⁿ 的精确值（用高精 × 单精反复乘 2）。
6. 编程题 — 高精度 A×B
输入两个不超过 500 位的正整数，输出它们的乘积。
🧠 本章小结
高精度运算 = 用数组/字符串模拟竖式计算
存储约定：a[1]=个位, a[len]=最高位（倒序存储）
四种基本运算：
加法：逐位加 + 进位 carry
减法：先比大小（确保大减小）+ 借位 borrow
乘法：高精×单精（进位用 long long）
高精×高精（先全部累加再统一进位）
除法：高精÷单精（从高位往低位，维护余数）
关键细节：
✓ 方向：加减乘从低位→高位，除从高位→低位
✓ 前导零：减法和除法后要清理
✓ 压位：进阶优化，每元素存 4 位📝 配套练习
共6题。加→减→乘→阶乘→快速幂，高精度运算阶梯式递进。。★核心（课堂必做） ◆拓展（课后练习）
💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 37 道◆拓展题，覆盖不同变式和细节。
配套练习
共6题。加→减→乘→阶乘→快速幂，高精度运算阶梯式递进。★核心（课堂必做） · ◆拓展（课后练习）
练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 37 道◆拓展题，覆盖不同变式和细节。
自查清单：
- [ ] 我理解高精度运算的存储约定（倒序）
- [ ] 我能独立实现高精度加法（含进位处理）
- [ ] 我能独立实现高精度减法（含大小比较和借位）
- [ ] 我能实现高精 × 单精和高精 × 高精
- [ ] 我能实现高精 ÷ 单精
- [ ] 我知道何时去除前导零，以及为什么要"先累加再统一进位"
🚀 下章预告：M5「暴力与基础技巧」到此收官！你从枚举进阶一路走来，掌握了模拟、双指针、前缀和、离散化和高精度——这些都是信息学竞赛的"基本功"。下一模块 M6，我们将进入算法的核心——排序与复杂度，正式开始讨论"算法的好坏"以及系统学习各种排序方法。准备好了吗？🚀