4.高精度计算
一、高精度算法（仅 C++ 需掌握）
核心背景
Java 有大整数类、Python 默认支持无限大数，C++ 需通过数组模拟大整数运算，适用于位数超 1e6 位的整数（数值范围远超long long）。
存储规则
- 逆序存储：将大整数的个位存在数组下标 0 位，高位依次往后存（如 123456 存为
[6,5,4,3,2,1]），方便进位 / 借位时在数组末尾操作（避免数组平移）。
1. 高精度加法（A + B，A、B ≥ 0）
思路
- 模拟人工加法：从个位开始，逐位相加，加上上一位进位，当前位取和的个位（
t%10），进位取和的十位（t/10）； - 处理边界：当 A 或 B 未遍历完时，未存在的位视为 0；遍历结束后若仍有进位，需在结果末尾补 1。
代码模板（结合 PDF 优化）
#include <vector>
using namespace std;// C = A + B，A、B逆序存储（个位在0位）
vector<int> add(vector<int> &A, vector<int> &B)
{vector<int> C;int t = 0; // 进位，初始为0for (int i = 0; i < A.size() || i < B.size(); i++) {if (i < A.size()) t += A[i];if (i < B.size()) t += B[i];C.push_back(t % 10); // 当前位结果t /= 10; // 更新进位}if (t) C.push_back(1); // 最后仍有进位return C;
}
测试案例
- 输入：A=11（存储为
[1,1]），B=99（存储为[9,9]） - 运算过程：
- 个位：1+9+0=10 → 存 0，进位 1；
- 十位：1+9+1=11 → 存 1，进位 1；
- 遍历结束，进位 1 补尾 → 结果
[0,1,1]，逆序输出为 110。
- 输出：110
2. 高精度减法（A - B，需满足 A ≥ B，A、B ≥ 0）
讲解思路
- 预处理：先通过
cmp函数判断 A 是否≥B，若 A<B 则计算-(B - A)； - 模拟人工减法：从个位开始，逐位相减（减去上一位借位），若当前位不够减则借位（+10），借位标记为 1；
- 去前导零：结果末尾若有连续 0（如 003→3），需删除（保留最后一个 0）。
代码模板（含 cmp 函数）
#include <vector>
using namespace std;// 判断A是否≥B（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; // 相等
}// C = A - B（A ≥ B）
vector<int> sub(vector<int> &A, vector<int> &B)
{vector<int> C;int t = 0; // 借位，初始为0（t=1表示上一位借了1）for (int i = 0; i < A.size(); i++) {t = A[i] - t; // 先减去上一位借位if (i < B.size()) t -= B[i]; // 减去B的当前位C.push_back((t + 10) % 10); // 处理不够减的情况t = t < 0 ? 1 : 0; // 更新借位}// 去前导零while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}
3. 高精度乘低精度（A × b，A ≥ 0，b ≥ 0，b 为 int 型）
讲解思路
- 模拟人工乘法：从个位开始，逐位与 b 相乘，加上上一位进位，当前位取乘积的个位（
t%10），进位取乘积的高位（t/10）； - 处理边界：遍历 A 的所有位后，若仍有进位，需将进位的每一位依次补到结果末尾。
代码模板
#include <vector>
using namespace std;// C = A × b，A逆序存储，b为低精度整数
vector<int> mul(vector<int> &A, int b)
{vector<int> C;int t = 0; // 进位，初始为0for (int i = 0; i < A.size() || t; i++){if (i < A.size()) t += A[i] * b;C.push_back(t % 10); // 当前位结果t /= 10; // 更新进位}// 去前导零（如A=0或b=0时）while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}
4. 高精度除低精度（A ÷ b = C ... r，A ≥ 0，b > 0，r 为余数）
讲解思路
- 模拟人工除法：从高位开始（与加减乘相反），用余数 ×10 加上当前位，当前位商为
余数÷b，余数更新为余数%b； - 处理存储：商的结果是正序存储，需逆序后与其他高精度运算统一格式；
- 去前导零：删除商的前导零（如 0112→112）。
代码模板
#include <vector>
#include <algorithm>
using namespace std;// A ÷ b = C（商）... r（余数），A逆序存储，C逆序输出
vector<int> div(vector<int> &A, int b, int &r)
{vector<int> C;r = 0; // 余数，初始为0// 从高位到低位遍历（A逆序存储，高位在末尾）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;
}