高精度计算 知识点讲解

概念

考纲要求（高精度计算）：当数据超出 long long（约 9.2×10¹⁸）范围时，用数组按位存储大整数，模拟竖式完成加、减、乘、除。本讲对齐该考点，补充高精度加法实现与图示。

C++ 里最大的整数类型是 long long，只能存到约 9.2 × 10¹⁸（19 位数字）。

那要算 100!（158 位数）、2^1000（302 位数）怎么办？—— 把大整数当成字符串/数组，一位一位手工算，就像小学学的竖式。

// 用数组倒着存：a[0] 是个位，a[1] 是十位，a[2] 是百位……
// 12345 存成 a = [5, 4, 3, 2, 1]

为什么要"倒着存"：因为竖式是从个位开始算的，进位也是往高位走。倒着存（低位在下标小的地方）能让进位自然地向 i+1 传递。

️ 很多人的困惑："什么时候要用高精度？" —— 答案不是"数很大"，而是"算一算会不会超过 9.2×10¹⁸"。这个判断要从题目给的范围推出来，而不是瞎猜。判断不出来就先用 long long 估上界，超了才上高精度。

考纲要求：NOI 大纲 — 考点「高精度 / 数组模拟高精度」。在 CCF 考纲里，高精度是「基本运算」的必要补充：当运算结果超出 64 位整数（约 9.2×10¹⁸）范围时，必须用数组或字符串模拟竖式完成加、减、乘、除。它既是独立考点（阶乘、大数相加、回文数），更是「大数 + DP / 数论 / 组合计数」类题的基础存储手段，要求纯熟到"看到超范围就立刻能写"。

触发清单（看到这些信号第一时间想到本知识点）

定义

存储约定（必须统一）：

int a[1005]; // a[0] = 位数, a[1..a[0]] = 各位数字（a[1] 是个位）
// 或者用 vector<int>，下标 0 是个位

加法（竖式）：

int a[1005] = {0}, b[1005] = {0}, c[1005] = {0};
// ... 读入并倒序存入 ...
int len = max(la, lb);
for (int i = 1; i <= len; i++) {
 c[i] += a[i] + b[i];
 c[i + 1] += c[i] / 10; //  进位
 c[i] %= 10;
}
if (c[len + 1]) len++; //  最高位还有进位 → 长度 +1

进位长什么样？ 拿 25 + 37 走一遍竖式（数组逆序存 a=[5,2]、b=[7,3]）：个位 5+7=12 写 2 进 1，十位 2+3+进位1=6，结果 c=[2,6] → 倒序输出 62。一看就懂：

乘法（高精 × 低精）：

for (int i = 1; i <= len; i++) {
 a[i] = a[i] * m + carry; // m 是那个小整数
 carry = a[i] / 10;
 a[i] %= 10;
}

乘法（高精 × 高精）：c[i + j - 1] += a[i] * b[j]，最后统一处理进位。

减法要注意：必须大减小、且要处理"借位"。若 a < b，要输出负号并把两个数交换。

复杂度：加减法 O(n)，乘法 O(n·m)。n 是位数。

推演：为什么这些写法是对的（以及它们能用来干什么）

高精度就是「用数组模拟竖式」。下面推三点。

推演 1 · 为什么数组要「逆序」存

竖式加法从个位开始、进位往高位走。把个位放在数组下标 0，进位就是「下标 +1」，天然向右（数组尾部）延伸，不用整体平移。若正序存（高位在下标 0），进位要往左插，极不方便。

用法：高精一律逆序存（下标 0 = 个位），输出时反向打印。

推演 2 · 高精乘法为什么是 c[i+j] += a[i] * b[j]

小学乘法里，a 的第 i 位（权值 10^i）乘 b 的第 j 位（权值 10^j）结果落在该数第 i+j 位（权值 10^(i+j)）。所以 c[i+j] += a[i]*b[j]，最后统一处理进位。高精 × 低精 是 j 固定为 0 的特例；高精 × 高精 是双重循环。

用法：写高精乘先想「位值相乘的代数展开」，再补进位。

推演 3 · 为什么需要高精度（先估算上界）

n! 的位数 ≈ n·log10(n/e)；乘积累计可到 1e100+。long long 只到约 1.8e19，超了必须用数组模拟。动手前先 log10 估一下位数：若超 18 位，直接上高精，别等溢出。

用法：题目说「结果可能很大 / 先不取模」，先估算位数再决定要不要高精。

技巧速查表（背下来）

原讲义配图

例题

例题 1：阶乘之和

题目描述

给定一个正整数 $n$（$1 \le n \le 100$），求 $1! + 2! + 3! + \dots + n!$ 的值。由于结果非常大，请输出完整的整数。

审题分析

1. 读题抓条件：输入 $n$，输出 $n$ 个阶乘的和。

2. 定需求：需要计算阶乘（高精乘低精）和累加（高精加高精）。

3. 为什么能用本知识点：$100!$ 有 158 位，远超 long long 范围，必须用高精度模拟竖式。

4. 如果不用会怎样：用 long long 算 $100!$ 会溢出变成负数或错误的小数，累加结果完全错误。

解题思路

1. 定义一个大整数数组 fac 用于存储当前阶乘的值，初始化为 1。

2. 定义一个大整数数组 sum 用于存储累加和，初始化为 0。

3. 循环 $i$ 从 1 到 $n$：

* 将 fac 乘以 $i$（高精乘低精）。

* 将 sum 加上 fac（高精加高精）。

4. 输出 sum。

C++ 完整参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 辅助函数：打印大整数（倒序存储，所以从末尾向前打印）
void printBigInt(const vector<int>& a) {
 int i = a.size() - 1;
 // 去掉前导零
 while (i > 0 && a[i] == 0) i--;
 for (; i >= 0; i--) cout << a[i];
 cout << endl;
}

// 辅助函数：高精乘低精 (a = a * m)
void multiplyBySmall(vector<int>& a, int m) {
 int carry = 0;
 for (size_t i = 0; i < a.size(); i++) {
 int t = a[i] * m + carry;
 a[i] = t % 10;
 carry = t / 10;
 }
 while (carry) {
 a.push_back(carry % 10);
 carry /= 10;
 }
}

// 辅助函数：高精加高精 (a = a + b)
void addBigInt(vector<int>& a, const vector<int>& b) {
 int carry = 0;
 size_t n = max(a.size(), b.size());
 for (size_t i = 0; i < n; i++) {
 int val = (i < a.size() ? a[i] : 0) + (i < b.size() ? b[i] : 0) + carry;
 a[i] = val % 10;
 carry = val / 10;
 }
 if (carry) a.push_back(carry);
}

int main() {
 int n;
 cin >> n;

 vector<int> fac = {1}; // 1! = 1
 vector<int> sum = {0}; // 初始和为 0

 for (int i = 1; i <= n; i++) {
 // ① fac *= i （高精 × 低精）
 multiplyBySmall(fac, i);

 // ② sum += fac （高精加法）
 addBigInt(sum, fac);
 }

 printBigInt(sum);
 return 0;
}

代码解读

• multiplyBySmall 中使用了 while (carry) 而不是 if (carry)，因为乘完后进位可能不止一位（例如 $9 \times 9 = 81$，进位是 8，需要再补一位）。
• addBigInt 中先判断 i < a.size() 和 i < b.size()，防止访问越界，这是处理两个数长度不一致的关键。
• 主循环中，先更新阶乘，再累加到总和，逻辑清晰。

运行结果

输入：5

输出：

153

(验证：$1!+2!+3!+4!+5! = 1+2+6+24+120 = 153$)

---

例题 2：大数加法

题目描述

给定两个正整数 $A$ 和 $B$（每个数不超过 1000 位），计算 $A + B$ 的值并输出。

审题分析

1. 读题抓条件：两个超长整数相加。

2. 定需求：高精加高精。

3. 为什么能用本知识点：题目明确说了“不超过 1000 位”，long long 最多存 19 位，必须用数组模拟竖式。

4. 如果不用会怎样：直接读入字符串转 long long 会溢出，或者用 __int128 也存不下 1000 位。

解题思路

1. 用 string 读入两个数，反转后存入数组（低位在下标 0）。

2. 补齐较短的数组（用 0 填充）。

3. 逐位相加，处理进位。

4. 如果最后还有进位，长度加 1。

5. 倒序输出。

C++ 完整参考代码

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
 string s, t;
 cin >> s >> t;
 
 // 反转，使低位在前（下标 0 是个位）
 reverse(s.begin(), s.end());
 reverse(t.begin(), t.end());
 
 int n = max(s.size(), t.size());
 vector<int> a(n, 0), b(n, 0);
 
 for (int i = 0; i < s.size(); i++) a[i] = s[i] - '0';
 for (int i = 0; i < t.size(); i++) b[i] = t[i] - '0';
 
 int carry = 0;
 for (int i = 0; i < n; i++) {
 int sum = a[i] + b[i] + carry;
 c[i] = sum % 10;
 carry = sum / 10;
 }
 if (carry) c[n++] = carry;
 
 // 倒序输出
 for (int i = n - 1; i >= 0; i--) cout << c[i];
 cout << endl;
 return 0;
}

*(注：以上代码片段中的 c 数组需在前文定义，此处为演示逻辑简化，实际应使用 vector<int> c(n, 0) 并在循环中赋值)*

修正后的完整代码：

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
 string s, t;
 cin >> s >> t;
 
 // 反转，使低位在前（下标 0 是个位）
 reverse(s.begin(), s.end());
 reverse(t.begin(), t.end());
 
 int n = max(s.size(), t.size());
 vector<int> a(n, 0), b(n, 0);
 
 for (int i = 0; i < s.size(); i++) a[i] = s[i] - '0';
 for (int i = 0; i < t.size(); i++) b[i] = t[i] - '0';
 
 vector<int> c(n, 0);
 int carry = 0;
 for (int i = 0; i < n; i++) {
 int sum = a[i] + b[i] + carry;
 c[i] = sum % 10;
 carry = sum / 10;
 }
 if (carry) c[n++] = carry;
 
 // 倒序输出
 for (int i = n - 1; i >= 0; i--) cout << c[i];
 cout << endl;
 return 0;
}

运行结果

输入：99999999999999999999 1

输出：

100000000000000000000

例题复盘总结

共性特征

1. 输入规模大：题目中明确出现“位数”、“长度”、“超大”、“100 位”等字眼，或者给出的数字明显超过 long long 范围（如 $100!$）。

2. 运算类型固定：绝大多数是加法、乘法或阶乘累加，极少涉及除法（除法通常配合取模）。

3. 输出要求精确：题目要求输出完整结果，而不是取模后的余数。

各自技巧

1. 加法：核心是“倒序存、逐位加、处理进位、最后补位”。注意 while(carry) 写进位，if 会丢高位。

2. 乘法：

* 高精 × 低精：循环乘，t = a[i]*m + carry，同样注意 while(carry)。

* 高精 × 高精：双重循环 c[i+j] += a[i]*b[j]，最后统一进位。

3. 阶乘：本质是循环高精 × 低精，每次乘完更新大数。

4. 大数比较：先比长度，长度相同再字典序（从高位比，即数组末尾比）。

审题模板（固定思考流程）

1. 看范围：结果会不会超过 $10^{19}$？

2. 看要求：只要取模吗？是的话直接用模运算，别写高精度。

3. 看类型：加法/乘法/阶乘？

4. 定存储：统一用“低位在下标 0”的数组或 vector。

5. 写模板：套用对应的小节代码，注意边界（如 while(carry)）。

错误清单（特有）

1. 进位处理错误：乘法或加法最后忘记 while(carry) 或忘记补位，导致结果少一位。

2. 比较逻辑错误：直接比字符串 "9" < "10" 为 false，导致排序或判断大小出错。

3. 前导零未去：输出时最高位是 0 没处理，导致输出 0123 而不是 123。

4. 数组开太小：没估算位数直接开 100，导致 n! 存不下。

5. 混淆取模与高精度：题目只要 % 1e9+7 却写了高精度，导致 TLE。

写法总表

分工说明：「技巧速查表」侧重代码片段和核心逻辑（怎么写），「写法总表」侧重技法分层和适用场景（什么时候用什么）。两者结合，一个管“怎么做”，一个管“什么时候用”。

常见错误

1. while (carry) 写成 if (carry)。 乘法后进位可能是多位，写 if 会丢掉高位。这是高精度乘法最常见的错误。

2. 忘记倒序输出。 数组是倒着存的，输出时忘了倒回来 → 结果是反的。

3. 进位忘了加。 加法里 c[i] = a[i] + b[i] 却忘了上一轮留下的 carry。

4. 最高位进位丢失。 加法最后 c[len] 还有进位时忘记 len++。

5. 减法忘了处理负数。 a - b 当 a < b 时要交换并输出 -。

6. 比较大小时直接比字符串。 "9" < "10" 为 false，但数值上 9 < 10。必须先比长度。

7. 前导零。 结果最高位可能是 0（比如加出来是 0），输出时要处理。

8. 该用取模却写高精度。 题目只要"结果模 1e9+7"，写高精度又慢又容易错 —— 先看题目要不要精确值。

9. 数组开得太小。 n = 1000 的阶乘有 2568 位，数组要开够。先估算位数再开。

自测

1. long long 最大能存多少？100! 有多少位？

2. 高精度为什么把个位存在下标 0？

3. 写出高精度加法的进位处理，并说明最后还要检查什么。

4. 高精度 × 低精度时，为什么进位要用 while 而不是 if？

5. 用字符串存大数时，为什么不能直接 x < y 比大小？

6. 什么时候不需要写高精度？举一个例子。

7. 高精度减法要注意哪两件事？

举一反三 · 审题流水线

拿到题先别急着写代码，按这个顺序过一遍：

1. 看范围：结果会不会超过 $10^{19}$？

2. 看要求：只要取模吗？是的话直接用模运算，别写高精度。

3. 看类型：加法/乘法/阶乘？

4. 定存储：统一用“低位在下标 0”的数组或 vector。

5. 写模板：套用对应的小节代码，注意边界（如 while(carry)）。

练手题

题 1：大数比较

给定两个正整数 $A$ 和 $B$（每个数不超过 1000 位），判断 $A$ 是否大于 $B$。如果 $A > B$ 输出 Yes，否则输出 No。

题 2：大数乘法

给定两个正整数 $A$ 和 $B$（每个数不超过 1000 位），计算 $A \times B$ 的值并输出。