高精度算法详解：加减乘除完全指南

在算法竞赛中，当整数超过基本数据类型的表示范围时，就需要使用高精度算法。本文详细介绍高精度加法、减法、乘法和除法的实现原理和完整代码。

1. 高精度算法简介

1.1 什么是高精度算法？

高精度算法（Big Integer）是用于处理超大整数运算的算法。在 C++ 中：

• int 类型范围： ~ （约 ）
• long long 类型范围： ~ （约 ）

当数字超过这些范围时，就需要使用高精度算法。

1.2 高精度的核心思想

基本原理： 用数组存储每一位数字，模拟手工运算的过程。

存储方式： 通常采用逆序存储（低位在前，高位在后），方便进位处理。

例如：数字 12345 存储为 [5, 4, 3, 2, 1]

1.3 适用场景

• 阶乘运算（如 ）
• 斐波那契数列的大数项
• 组合数学中的大数计算
• 密码学相关算法

---

2. 高精度加法

2.1 算法思路

模拟小学竖式加法：

1. 从最低位开始逐位相加
2. 处理进位（carry）
3. 如果最高位有进位，需要增加一位

时间复杂度： ，其中 是较长数字的位数

2.2 图解示例

  1 2 3 4 5
+   9 8 7 6
-----------
  2 2 2 2 1

2.3 完整代码实现

#include <bits/stdc++.h>
using namespace std;

// 高精度加法：A + B
vector<int> add(vector<int> &A, vector<int> &B) {
    vector<int> C;  // 存储结果
    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];
        C.push_back(carry % 10);  // 当前位的结果
        carry /= 10;  // 进位
    }
    
    // 处理最后的进位
    if (carry) C.push_back(carry);
    
    return C;
}

int main() {
    string a, b;
    cin >> a >> b;
    
    // 将字符串转换为数组（逆序存储）
    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    
    // 执行加法
    vector<int> C = add(A, B);
    
    // 输出结果（逆序输出）
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    cout << endl;
    
    return 0;
}

---

3. 高精度减法

3.1 算法思路

模拟小学竖式减法：

1. 确保被减数 ≥ 减数（需要比较大小）
2. 从最低位开始逐位相减
3. 处理借位（borrow）
4. 去除前导零

时间复杂度：

3.2 图解示例

  1 2 3 4 5
-   9 8 7 6
-----------
  1 1 4 6 9

3.3 完整代码实现

#include <bits/stdc++.h>
using namespace std;

// 判断 A >= B
bool cmp(vector<int> &A, vector<int> &B) {
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; i--) {
        if (A[i] != B[i]) return A[i] > B[i];
    }
    return true;  // A == B
}

// 高精度减法：A - B（假设 A >= B）
vector<int> sub(vector<int> &A, vector<int> &B) {
    vector<int> C;
    int borrow = 0;  // 借位
    
    for (int i = 0; i < A.size(); i++) {
        borrow = A[i] - borrow;
        if (i < B.size()) borrow -= B[i];
        C.push_back((borrow + 10) % 10);
        borrow = (borrow < 0) ? 1 : 0;  // 是否需要借位
    }
    
    // 去除前导零
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

int main() {
    string a, b;
    cin >> a >> b;
    
    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    
    // 确保 A >= B
    if (cmp(A, B)) {
        vector<int> C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    } else {
        // A < B，输出负号
        cout << "-";
        vector<int> C = sub(B, A);
        for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    }
    cout << endl;
    
    return 0;
}

---

4. 高精度乘法

4.1 算法思路

情况一：高精度 × 低精度（最常用）

模拟竖式乘法：

1. 用高精度数的每一位乘以低精度数
2. 处理进位
3. 时间复杂度：

情况二：高精度 × 高精度

使用竖式乘法的思想，时间复杂度：

4.2 图解示例（高精度 × 低精度）

  1 2 3
×     7
-------
  8 6 1

4.3 完整代码实现

4.3.1 高精度 × 低精度

#include <bits/stdc++.h>
using namespace std;

// 高精度乘法：A × b（b 是普通整数）
vector<int> mul(vector<int> &A, int b) {
    vector<int> C;
    int carry = 0;
    
    for (int i = 0; i < A.size() || carry; i++) {
        if (i < A.size()) carry += A[i] * b;
        C.push_back(carry % 10);
        carry /= 10;
    }
    
    // 去除前导零（处理 b = 0 的情况）
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

int main() {
    string a;
    int b;
    cin >> a >> b;
    
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    
    vector<int> C = mul(A, b);
    
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    cout << endl;
    
    return 0;
}

4.3.2 高精度 × 高精度

#include <bits/stdc++.h>
using namespace std;

// 高精度乘法：A × B
vector<int> mul(vector<int> &A, vector<int> &B) {
    vector<int> C(A.size() + B.size(), 0);  // 结果最多 A.size() + B.size() 位
    
    // 模拟竖式乘法
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < B.size(); j++) {
            C[i + j] += A[i] * B[j];
        }
    }
    
    // 处理进位
    int carry = 0;
    for (int i = 0; i < C.size(); i++) {
        carry += C[i];
        C[i] = carry % 10;
        carry /= 10;
    }
    
    // 去除前导零
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

int main() {
    string a, b;
    cin >> a >> b;
    
    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    
    vector<int> C = mul(A, B);
    
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    cout << endl;
    
    return 0;
}

---

5. 高精度除法

5.1 算法思路

高精度 ÷ 低精度（最常用）

模拟手工长除法：

1. 从高位到低位处理
2. 每次取当前位和余数组成新的被除数
3. 计算商和余数
4. 注意：结果需要翻转（因为从高位到低位计算）

时间复杂度：

5.2 图解示例

1 2 3 4 ÷ 5 = 246 ... 4

5.3 完整代码实现

#include <bits/stdc++.h>
using namespace std;

// 高精度除法：A ÷ b（b 是普通整数）
// 返回商 C 和余数 r
vector<int> div(vector<int> &A, int b, int &r) {
    vector<int> C;
    r = 0;  // 余数
    
    // 从高位到低位处理（所以要倒着遍历）
    for (int i = A.size() - 1; i >= 0; i--) {
        r = r * 10 + A[i];  // 组成新的被除数
        C.push_back(r / b);  // 当前位的商
        r %= b;  // 更新余数
    }
    
    // 反转结果（因为是从高位到低位计算的）
    reverse(C.begin(), C.end());
    
    // 去除前导零
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

int main() {
    string a;
    int b;
    cin >> a >> b;
    
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    
    int r;  // 余数
    vector<int> C = div(A, b, r);
    
    // 输出商
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    cout << endl;
    
    // 输出余数
    cout << "余数: " << r << endl;
    
    return 0;
}

---

6. 高精度算法模板总结

6.1 快速使用模板

// 高精度加法
vector<int> add(vector<int> &A, vector<int> &B);

// 高精度减法（A >= B）
vector<int> sub(vector<int> &A, vector<int> &B);

// 高精度乘法（A × b）
vector<int> mul(vector<int> &A, int b);

// 高精度除法（A ÷ b，返回商和余数）
vector<int> div(vector<int> &A, int b, int &r);

6.2 常用技巧

1. 字符串转数组：

   vector<int> A;
   for (int i = a.size() - 1; i >= 0; i--) 
       A.push_back(a[i] - '0');

2. 数组转字符串输出：

   for (int i = C.size() - 1; i >= 0; i--) 
       cout << C[i];

3. 去除前导零：

   while (C.size() > 1 && C.back() == 0) 
       C.pop_back();

6.3 注意事项

1. 存储方式： 采用逆序存储（低位在前）
2. 边界情况： 注意处理 0、负数、前导零
3. 内存优化： 可以使用 vector<int> 或 string 存储
4. 进制选择： 可以使用万进制优化（存储 4 位一组）

---

7. 经典例题

7.1 阶乘计算

问题： 计算 （）

#include <bits/stdc++.h>
using namespace std;

vector<int> mul(vector<int> &A, int b) {
    vector<int> C;
    int carry = 0;
    for (int i = 0; i < A.size() || carry; i++) {
        if (i < A.size()) carry += A[i] * b;
        C.push_back(carry % 10);
        carry /= 10;
    }
    return C;
}

int main() {
    int n;
    cin >> n;
    
    vector<int> result = {1};  // 初始化为 1
    
    // 计算 n!
    for (int i = 2; i <= n; i++) {
        result = mul(result, i);
    }
    
    // 输出结果
    for (int i = result.size() - 1; i >= 0; i--) 
        cout << result[i];
    cout << endl;
    
    return 0;
}

7.2 斐波那契数列

问题： 计算第 个斐波那契数（）

#include <bits/stdc++.h>
using namespace std;

vector<int> add(vector<int> &A, vector<int> &B) {
    vector<int> C;
    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];
        C.push_back(carry % 10);
        carry /= 10;
    }
    if (carry) C.push_back(carry);
    return C;
}

int main() {
    int n;
    cin >> n;
    
    vector<int> f1 = {1}, f2 = {1};
    
    for (int i = 3; i <= n; i++) {
        vector<int> f3 = add(f1, f2);
        f1 = f2;
        f2 = f3;
    }
    
    for (int i = f2.size() - 1; i >= 0; i--) 
        cout << f2[i];
    cout << endl;
    
    return 0;
}

---

8. 性能优化

8.1 万进制优化

将每 4 位十进制数存为一个单位，可以提升 4 倍效率：

// 万进制高精度加法
vector<int> add(vector<int> &A, vector<int> &B) {
    vector<int> C;
    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];
        C.push_back(carry % 10000);
        carry /= 10000;
    }
    if (carry) C.push_back(carry);
    return C;
}

8.2 使用 Python

对于高精度运算，Python 原生支持大整数：

# Python 中直接计算大整数
a = int(input())
b = int(input())
print(a + b)
print(a * b)

---

9. 总结

运算	时间复杂度	难度	适用场景
加法		⭐⭐	基础运算
减法		⭐⭐⭐	需要比较大小
乘法（×低精度）		⭐⭐⭐	最常用
乘法（×高精度）		⭐⭐⭐⭐	两个大数相乘
除法		⭐⭐⭐⭐	需要处理余数

学习建议：

1. 先掌握高精度加法和乘法（最常用）
2. 理解逆序存储的原因
3. 多练习处理边界情况
4. 熟练使用模板

推荐练习题：

• 洛谷 P1009 阶乘之和
• 洛谷 P1303 A×B Problem
• 洛谷 P2142 高精度减法
• AcWing 791-794 高精度四则运算

---

参考资料：

• 《算法竞赛进阶指南》
• 洛谷题解
• AcWing 算法基础课

---

💡 提示： 高精度算法是算法竞赛的基础工具，建议将模板代码整理成代码库，方便比赛时快速调用！