Appearance
第4章 高精度
🎯 本章学习目标
通过本章的学习，你将能够：
- 理解高精度概念：知道什么时候需要高精度，理解数组模拟大数的原理
- 掌握倒序存储：理解为什么要倒序存储，能正确进行字符串与数组的转换
- 实现高精度加法：熟练掌握高精度加法的进位处理
- 实现高精度减法：掌握借位处理和大小比较，能去掉前导零
- 实现高精度乘法：掌握高精度乘低精度和高精度乘高精度
- 实现高精度除法：掌握高精度除以低精度的试商和余数处理
- 处理边界情况：能处理进位溢出、前导零、结果为 0 等特殊情况
- 分析代码输出：能快速分析高精度代码的中间结果
- 应对代码填空：熟练掌握高精度加减乘除的经典代码填空
- 解决实际问题：能用高精度算法解决阶乘、大数求和等实际问题
🗺️ 本章知识图谱
高精度运算
├── 基础概念
│ ├── 为什么需要高精度（long long 不够用）
│ ├── 核心思想：数组模拟手工竖式
│ └── 倒序存储（个位在0位，进位方便）
├── 高精度加法
│ ├── 思路：逐位相加 + 进位
│ ├── 步骤：倒序存 → 逐位加 → 处理进位 → 追加最高进位
│ └── 关键：循环结束后 carry!=0 要追加
├── 高精度减法
│ ├── 思路：逐位相减 + 借位
│ ├── 前提：先比较大小，大减小
│ ├── 借位：不够减就向高位借1当10
│ └── 去前导零（结果可能有很多前导零）
├── 高精度乘法
│ ├── 高精 × 低精
│ │ ├── 每一位乘低精度数 + 进位
│ │ └── 进位可能不止一位
│ └── 高精 × 高精
│ ├── 第i位 × 第j位 → 结果第i+j位
│ └── 最后统一处理进位
├── 高精度除法
│ ├── 高精 ÷ 低精
│ │ ├── 正序存储（从高位开始算）
│ │ ├── 余数×10 + 当前位 → 试商
│ │ └── 去前导零
│ └── 余数保留
└── 常见应用
├── 大数阶乘
├── 斐波那契大数版
└── 大数求和一、为什么需要高精度？
C++ 基本数据类型有范围限制：
int：最大约 2×10⁹long long：最大约 9×10¹⁸
当运算结果超过 long long 范围时（如 100 的阶乘、两个 200 位数的加法），就需要用数组模拟手工竖式运算，这就是高精度算法。
核心存储方式：倒序存储
将数字的个位存在数组下标 0，十位在下标 1，以此类推。这样进位和追加高位都非常方便。
数字：123456
数组（正序）： [1][2][3][4][5][6] ← 进位需要在数组头部插入，麻烦
数组（倒序）： [6][5][4][3][2][1] ← 进位直接追加到末尾，方便！
↑个位二、高精度加法
思路：
- 两个数都倒序存入数组
- 从低位到高位逐位相加，处理进位
- 最后若有进位，追加到结果末尾
cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 高精度加法：a + b，输入为字符串，返回结果字符串
string bigAdd(const string& a, const string& b) {
vector<int> va, vb;
// 倒序存储：个位在下标 0
for (int i = a.size() - 1; i >= 0; i--)
va.push_back(a[i] - '0');
for (int i = b.size() - 1; i >= 0; i--)
vb.push_back(b[i] - '0');
vector<int> result;
int carry = 0; // 进位
int maxLen = max(va.size(), vb.size());
for (int i = 0; i < maxLen; i++) {
int sum = carry;
if (i < (int)va.size()) sum += va[i];
if (i < (int)vb.size()) sum += vb[i];
result.push_back(sum % 10); // 当前位
carry = sum / 10; // 进位
}
if (carry != 0) result.push_back(carry); // 处理最高位进位
// 倒序输出
string ans;
for (int i = result.size() - 1; i >= 0; i--)
ans += (char)('0' + result[i]);
return ans;
}
int main() {
string a, b;
cin >> a >> b;
cout << bigAdd(a, b) << endl;
return 0;
}⚠️ 易错点：
- 循环结束后不要忘记检查
carry，可能还有最高位的进位！- 输入字符串转数字时用
a[i] - '0'，不要直接存字符。va.size()返回size_t（无符号类型），与int比较时建议强转，避免警告。
三、高精度减法
思路：
- 先比较两个数的大小，确定结果正负
- 用大数减小数，逐位相减，不够减则借位
- 去掉结果中的前导零
cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 比较两个正数字符串的大小：a >= b 返回 true
bool isGreaterOrEqual(const string& a, const string& b) {
if (a.size() != b.size()) return a.size() > b.size();
return a >= b; // 长度相同时按字典序比较即为数值大小
}
// 高精度减法：a - b（保证 a >= b）
string bigSub(const string& a, const string& b) {
vector<int> va, vb;
for (int i = a.size() - 1; i >= 0; i--)
va.push_back(a[i] - '0');
for (int i = b.size() - 1; i >= 0; i--)
vb.push_back(b[i] - '0');
vector<int> result;
int borrow = 0; // 借位
for (int i = 0; i < (int)va.size(); i++) {
int diff = va[i] - borrow;
if (i < (int)vb.size()) diff -= vb[i];
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
result.push_back(diff);
}
// 去掉前导零（倒序存储下，即去掉末尾的零）
while (result.size() > 1 && result.back() == 0)
result.pop_back();
string ans;
for (int i = result.size() - 1; i >= 0; i--)
ans += (char)('0' + result[i]);
return ans;
}
int main() {
string a, b;
cin >> a >> b;
if (isGreaterOrEqual(a, b)) {
cout << bigSub(a, b) << endl;
} else {
cout << "-" << bigSub(b, a) << endl;
}
return 0;
}⚠️ 易错点：
- 必须先比较大小，负数结果要加负号，并用大数减小数。
- 去前导零时注意保留一个
0（当结果为 0 时），不能把所有位都删光！条件result.size() > 1保证至少留一位。
四、高精度乘法
高精度乘法分两种：高精度 × 低精度（一个大数乘一个普通整数）和高精度 × 高精度（两个大数相乘）。
4.1 高精度 × 低精度
cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 高精度 a 乘以低精度 b（b 为普通整数，0 <= b <= 1e9）
string bigMulSmall(const string& a, int b) {
if (b == 0) return "0"; // 乘以 0 直接返回
vector<int> va;
for (int i = a.size() - 1; i >= 0; i--)
va.push_back(a[i] - '0');
vector<int> result;
long long carry = 0;
for (int i = 0; i < (int)va.size() || carry != 0; i++) {
long long product = carry;
if (i < (int)va.size()) product += (long long)va[i] * b;
result.push_back(product % 10);
carry = product / 10;
}
string ans;
for (int i = result.size() - 1; i >= 0; i--)
ans += (char)('0' + result[i]);
return ans;
}
int main() {
string a;
int b;
cin >> a >> b;
cout << bigMulSmall(a, b) << endl;
return 0;
}4.2 高精度 × 高精度（竖式乘法）
两个大数相乘，逐位相乘后累加到对应位置，最后统一处理进位。
1 2 3 （倒序存储：[3,2,1]）
× 4 5 （倒序存储：[5,4]）
-------
6 1 5 （3×5=15, 2×5=10, 1×5=5）
4 9 2 （3×4=12, 2×4=8, 1×4=4，左移一位）
-------
5 5 3 5规律：第 i 位 × 第 j 位的结果，累加到第 i+j 位。
cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 高精度 × 高精度
string bigMul(const string& a, const string& b) {
if (a == "0" || b == "0") return "0";
int n = a.size(), m = b.size();
vector<int> va(n), vb(m);
for (int i = 0; i < n; i++) va[i] = a[n - 1 - i] - '0';
for (int i = 0; i < m; i++) vb[i] = b[m - 1 - i] - '0';
// 结果数组，最多 n+m 位
vector<int> result(n + m, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
result[i + j] += va[i] * vb[j];
}
}
// 统一处理进位
int carry = 0;
for (int i = 0; i < n + m; i++) {
int sum = result[i] + carry;
result[i] = sum % 10;
carry = sum / 10;
}
// 去掉前导零
int len = n + m - 1;
while (len > 0 && result[len] == 0) len--;
string ans;
for (int i = len; i >= 0; i--)
ans += (char)('0' + result[i]);
return ans;
}
int main() {
string a, b;
cin >> a >> b;
cout << bigMul(a, b) << endl;
return 0;
}⚠️ 易错点：
- 竖式乘法中
result[i+j] += va[i] * vb[j]，先累加后进位，不要边乘边进位（容易出错）。- 结果数组大小开
n + m位即可（两个 n、m 位数相乘最多 n+m 位）。- 高精度×低精度中，
b可能较大，用long long存中间乘积和进位防止溢出。
五、高精度除法（高精度 ÷ 低精度）
GESP 五级只要求掌握高精度除以低精度（高精度÷高精度不在五级考纲范围内）。
思路： 从高位到低位逐位试商，余数带入下一位：
____567___
12 ) 6804
60 ← 6÷12 不够，商0；68÷12=5余8
---
80 ← 余数8带下一位0 → 80÷12=6余8
72
---
84 ← 余数8带下一位4 → 84÷12=7余0
84
--
0cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 高精度 a 除以低精度 b，返回 {商, 余数}
pair<string, int> bigDivSmall(const string& a, int b) {
vector<int> result;
int remainder = 0; // 余数
for (int i = 0; i < (int)a.size(); i++) {
int cur = remainder * 10 + (a[i] - '0'); // 余数×10 + 当前位
result.push_back(cur / b); // 商
remainder = cur % b; // 更新余数
}
// 去掉前导零（正序存储下，去掉开头的零）
int start = 0;
while (start < (int)result.size() - 1 && result[start] == 0)
start++;
string quotient;
for (int i = start; i < (int)result.size(); i++)
quotient += (char)('0' + result[i]);
return {quotient, remainder};
}
int main() {
string a;
int b;
cin >> a >> b;
pair<string, int> result = bigDivSmall(a, b);
cout << "商: " << result.first << endl;
cout << "余数: " << result.second << endl;
return 0;
}⚠️ 易错点：
- 除法是正序处理（从高位到低位），与加减乘的倒序不同，这是最容易搞混的地方！
- 余数必须
×10后再带下一位，即remainder * 10 + 当前位数字。- 商的前导零要去掉，但结果为 0 时保留一个
0。
🎯 考试常见考法：给出一段高精度除法代码，挖空
cur = remainder * 10 + (a[i] - '0')这行，考查对试商过程的理解。
六、高精度四种运算对比
| 运算 | 存储方式 | 处理方向 | 核心操作 | 特殊处理 |
|---|---|---|---|---|
| 加法 | 倒序 | 低位→高位 | 逐位相加 + 进位 | 循环后检查 carry |
| 减法 | 倒序 | 低位→高位 | 逐位相减 + 借位 | 比较大小、去前导零 |
| 乘法（×低精度） | 倒序 | 低位→高位 | 逐位相乘 + 进位 | 乘 0 特判 |
| 乘法（×高精度） | 倒序 | 低位→高位 | i+j 位累加 + 统一进位 | 结果开 n+m 位 |
| 除法（÷低精度） | 正序 | 高位→低位 | 余数×10+当前位试商 | 去商的前导零 |
🔑 一句话记忆：加减乘倒着来，除法正着来；进位加、借位减、乘积累加、余数×10。
七、📝 实战练习
练习题 1（单选题）
题目： 用高精度加法计算 99999999999999999999 + 1，结果是多少？
A. 100000000000000000000 B. 99999999999999999999 C. 10000000000000000000 D. 1000000000000000000000
🔑 点击查看答案与解析
答案： A
解析： 20 个 9 加 1 等于 1 后面跟 20 个 0，即 10^20 = 100000000000000000000，共 21 位。
用代码模拟：最低位 9+1=10，写 0 进 1；进位逐位传递，每一位都是 9+1=10，最终最高位产生进位 1，结果为 1 后跟 20 个 0。这道题考查的就是循环结束后 carry != 0 时追加进位的处理——如果漏掉这一步，结果会错误地变成 20 个 0。
💡 这道题如果用
long long直接计算会溢出（long long最大约 9.2×10¹⁸），这正是高精度存在的意义。
练习题 2（判断题）
题目： 高精度加法中，数字应该正序存储在数组中（最高位在下标 0 处），这样符合我们的阅读习惯。（ ）
🔑 点击查看答案与解析
答案： 错误 ❌
解析： 高精度运算应该倒序存储——个位存在下标 0 处。原因是：
- 加减乘的进位都是从低位（个位）向高位进行的
- 倒序存储时，进位可以直接
push_back到数组末尾 - 如果正序存储，进位需要在数组头部插入，非常麻烦
🍎 生活比喻：就像列竖式计算——我们从个位开始算，一步一步往高位走。倒序存储就是让数组的"开头"对应竖式的"右边"（个位）。
练习题 3（单选题）
题目： 高精度减法 1000 - 1 的结果数组（倒序存储）是？（ ）
A. [9, 9, 9]
B. [0, 0, 0, 1]
C. [9, 9, 9, 0]
D. [1, 0, 0, 0]
🔑 点击查看答案与解析
答案： A
解析：
1000 - 1 = 999
倒序存储（个位在 0 位）：
- 个位：9 → 下标 0
- 十位：9 → 下标 1
- 百位：9 → 下标 2
结果数组是 [9, 9, 9]，选 A。
🔥 关键考点：减法后要去前导零（这里对应的是数组末尾的零）。1000 - 1 计算过程中千位的 1 被借位后变成 0，最后要去掉，所以结果只有 3 位。
练习题 4（单选题）
题目： 高精度乘法中，一个 n 位的数乘以一个 m 位的数，结果最多有多少位？（ ）
A. n + m
B. n + m - 1
C. n × m
D. max(n, m)
🔑 点击查看答案与解析
答案： A
解析：
n 位最大值 = 10ⁿ - 1，m 位最大值 = 10ᵐ - 1 (10ⁿ - 1) × (10ᵐ - 1) < 10ⁿ × 10ᵐ = 10ⁿ⁺ᵐ
10ⁿ⁺ᵐ 是 1 后面跟 n+m 个 0，共 n+m+1 位，但乘积严格小于它，所以最多 n+m 位。
例如：99（2位）× 99（2位）= 9801（4位）= 2+2 位
选 A。
💡 最少位数是 n+m-1（比如 10×10=100，2+2-1=3 位）。
练习题 5（单选题）
题目： 关于高精度除法（高精度 ÷ 低精度），下列说法错误的是？（ ）
A. 除法从高位开始计算，和加减乘不同
B. 每一步的余数要乘以 10 加上下一位再试商
C. 除法也需要倒序存储
D. 商的前面可能有前导零需要去掉
🔑 点击查看答案与解析
答案： C
解析：
- A 正确 ✅：加减乘从低位（个位）开始，除法从高位开始
- B 正确 ✅：这是除法的核心步骤——余数×10+下一位
- C 错误 ❌：除法从高位开始算，所以通常用正序存储（或用倒序但从后往前算）
- D 正确 ✅：比如 1000 ÷ 5 = 0200，前面的 0 要去掉
💡 记忆口诀：加减乘倒着来，除法正着来。就像手工计算——加法从右往左加，除法从左往右除。
练习题 6（判断题）
题目： 高精度加法结果也需要去除前导零。（ ）
🔑 点击查看答案与解析
答案： 错误 ❌
解析： 加法是从低位往高位算，进位只会在最高位产生，不会出现前导零。前导零问题主要出现在减法（借位可能导致高位变零）和除法（商的高位可能是零）中。
⚠️ 注意：但如果两个数都是 0，加法结果也是 0，这不叫"前导零"，而是正常的结果。
练习题 7（程序阅读题）
题目： 阅读高精度加法代码片段，循环结束后 carry = 1 时，应该执行什么操作？（ ）
cpp
vector<int> add(vector<int>& a, vector<int>& b) {
vector<int> res;
int carry = 0;
for (int i = 0; i < a.size() || i < b.size(); i++) {
if (i < a.size()) carry += a[i];
if (i < b.size()) carry += b[i];
res.push_back(carry % 10);
carry /= 10;
}
// 循环结束后，carry = 1
____?____
return res;
}A. 什么都不用做
B. res.push_back(carry)
C. res.insert(res.begin(), carry)
D. carry = 0
🔑 点击查看答案与解析
答案： B
解析：
循环结束后如果 carry != 0，说明最高位还有进位，需要追加到结果的末尾（也就是最高位）。
因为是倒序存储，数组末尾对应数字的最高位，所以用 push_back 就可以了。
选 B。
🔥 高频考点：这是高精度加法最经典的代码填空题——循环结束后别忘了处理最后的进位！999 + 2 = 1001，如果漏掉这一步，结果就变成 001 了。
练习题 8（编程题）
题目： 请编写程序，计算 n 的阶乘（n!），其中 1 ≤ n ≤ 50。
由于结果可能很大，请使用高精度乘法（数组存储）。
输入：一个整数 n
输出：n! 的值
样例输入：10
样例输出：3628800
🔑 点击查看答案与解析
参考答案：
cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> res;
res.push_back(1); // 初始结果为 1
for (int i = 2; i <= n; i++) {
int carry = 0;
for (int j = 0; j < res.size(); j++) {
int product = res[j] * i + carry;
res[j] = product % 10;
carry = product / 10;
}
// 处理剩余进位
while (carry != 0) {
res.push_back(carry % 10);
carry /= 10;
}
}
// 倒序输出
for (int i = res.size() - 1; i >= 0; i--) {
cout << res[i];
}
cout << endl;
return 0;
}解析：
阶乘 = 1 × 2 × 3 × ... × n，这是高精度乘低精度的经典应用：
- 初始结果为 1（存在数组中，倒序存储）
- 从 2 乘到 n，每一步都是高精度数组 × 一个整数
- 乘完后处理进位（进位可能不止一位，用 while 循环）
- 最后倒序输出结果
时间复杂度：O(n × len)，len 是当前结果的位数。
💡 50! 大约有 65 位，100! 有 158 位，早就超过 long long 了，必须用高精度。
八、📊 考点总结表
| 考点 | 重要程度 | 出题形式 | 易错点 |
|---|---|---|---|
| 倒序存储原理 | ⭐⭐⭐⭐ | 选择/判断 | 为什么要倒序搞不清楚 |
| 高精度加法（进位） | ⭐⭐⭐⭐⭐ | 编程题/代码填空 | 漏掉最后的进位 |
| 高精度减法（借位） | ⭐⭐⭐⭐ | 编程题 | 忘记比较大小；前导零没去干净 |
| 减法的大小比较 | ⭐⭐⭐⭐ | 选择/编程 | 不知道先比较大小再减 |
| 高精 × 低精 | ⭐⭐⭐⭐ | 编程题/代码填空 | 进位是多位数，要用while |
| 高精 × 高精 | ⭐⭐⭐ | 编程题 | 结果数组位置 i+j 搞不清 |
| 高精 ÷ 低精 | ⭐⭐⭐ | 代码填空/程序阅读 | 从高位开始算；余数×10+下一位 |
| 前导零处理 | ⭐⭐⭐⭐ | 判断/代码填空 | 加法不需要，减法除法需要 |
| 结果位数估算 | ⭐⭐⭐ | 选择 | 乘法最多 n+m 位 |
| 阶乘高精度实现 | ⭐⭐⭐⭐ | 编程题 | 经典应用，必须掌握 |
⭐ 必背速记卡
┌─────────────────────────────────────────────┐
│ 高精度运算 · 必背速记卡 │
├─────────────────────────────────────────────┤
│ 1. long long 装不下时，用数组模拟高精度 │
│ 2. 加减乘：倒序存储，个位在下标 0 │
│ 3. 除法：正序存储，从高位开始算 │
│ 4. 加法：逐位相加，carry%10留，carry/=10进 │
│ 5. 加法循环结束，carry!=0 要追加到末尾 │
│ 6. 减法：先比大小，大减小，不够减就借位 │
│ 7. 减法借位：高位减1，当前位加10 │
│ 8. 减法结果要去前导零（数组末尾的零） │
│ 9. 乘法：n位 × m位，结果最多 n+m 位 │
│ 10. 高精×低精：每一位乘 + 进位 │
│ 11. 高精×高精：i位×j位 → 结果i+j位 │
│ 12. 除法：余数×10 + 下一位 → 试商 │
│ 13. 除法结果也要去前导零 │
│ 14. 输出时倒序输出（从数组末尾往头输出） │
│ 15. 阶乘是高精度乘法的经典应用 │
└─────────────────────────────────────────────┘