- 高精度运算
- 1. 算法基本思想
- 2. 高精度运算算法模板（理解背诵）
- 3. 应用：模板题
- （1）高精度加法
- （2）高精度减法
- （3）高精度乘法
- （4）高精度除法
Java 和 Python 不用考虑高精度运算，因为 Java 有大整数类，Python 数据默认是无限大，而 C++ 遇到超长位数的（例如有 1 0 6 10^6 106 位的整数）的加减乘除，并没有数据类型去匹配，也无法进行存储、运算，通常会出现数据溢出的情况，这时候就需要考虑使用高精度运算算法。
高精度运算，是指参与运算的数（加数，减数，因子等）范围大大超出了标准数据类型（整型，实型）能表示的范围的运算『例如，求两个 1 0 6 10^6 106 位的数的和』。这时，就要用到高精度算法了。本文的高精度运算的算法包括了加法、减法、乘法以及除法。
- 高精度加法（A + B）：两个 ≤ 1 0 6 ≤10^6 ≤106 位的数的和；
- 高精度减法（A - B）：两个 ≤ 1 0 6 ≤10^6 ≤106 位的数的差；
- 高精度乘法（A * a）：一个 ≤ 1 0 6 ≤10^6 ≤106 位的数乘以一个 ≤ 10000 ≤10000 ≤10000 的小整数所得的结果；
- 高精度除法（A / a）：一个 ≤ 1 0 6 ≤10^6 ≤106 位的数除以一个 ≤ 10000 ≤10000 ≤10000 的小整数所得的商和余数。
1. 算法基本思想
- 算法思想：
- 大整数的存储问题：我们将大整数的每一位存到数组里，并按照『个位 → 十位 → 百位 → . . . ... ...』的顺序依次存入数组，下标对应着『0 → 1 → 2 → . . . ... ...』，这是因为考虑到加法、乘法会存在 进位 ，在数组某位补上一位会比在数组最前面补上一位更容易。
- 运算方法：模拟人的运算过程。
- 高精度加法：从大整数的个位开始加，每一位加的过程看做为『 A i + B i + t A_i + B_i + t Ai+Bi+t』，『 t = 0 或 1 t = 0 或 1 t=0或1』 为被进位。若『 A i A_i Ai』或者『 B i B_i Bi』不存在，则将其看做为『 0 0 0』即可。
- 高精度减法：前提保证『 A ≥ B A ≥ B A≥B』。从大整数的个位开始减，每一位减的过程看做为『 A i − B i − t A_i - B_i - t Ai−Bi−t』，『 t = 0 或 1 t = 0 或 1 t=0或1』 为被借位。这里有两种情况：一是『 A i − B i − t ≥ 0 A_i - B_i - t ≥ 0 Ai−Bi−t≥0』，直接减；二是『 A i − B i − t < 0 A_i - B_i - t < 0 Ai−Bi−t<0』，则需要借位，答案为『 A i − B i − t + 10 A_i - B_i - t + 10 Ai−Bi−t+10』。
- 高精度乘法：只考虑『一个高精度大整数 A A A 乘以一个小整数 a a a』。从大整数的个位开始乘，每一位乘的过程看做为『 ( A i ∗ a + t ) % 10 (A_i *a + t)%10 (Ai∗a+t)%10』，『 t t t』 为被进位，而下一位的被进位为『 t = ( A i ∗ a + t ) / 10 t=(A_i *a + t)/10 t=(Ai∗a+t)/10』。
- 高精度除法：只考虑『一个高精度大整数 A A A 除以一个小整数 a a a』。从大整数的最高位开始除，最高位除的过程看做为『 A i / a A_i /a Ai/a，商为 r e s i res_i resi，余数为 r i r_i ri』；下一位除的过程看做『 ( r ∗ 10 + A i − 1 ) / a (r*10+A_{i - 1})/a (r∗10+Ai−1)/a，商为 r e s i − 1 res_{i-1} resi−1，余数为 r i − 1 r_{i-1} ri−1』；以此类推可得最终大整数除以小整数的商和余数。
- 建议结合代码来理解以上算法思路。
2. 高精度运算算法模板（理解背诵）
【高精度加法】
vectorBigInt_add(vector &A, vector &B) { if (A.size() < B.size()) return add(B, A); vector C; int t = 0; for (int i = 0; i < A.size(); i ++ ) { t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(t); return C; }
【高精度减法】
// 判断是否 A >= B bool cmp(vector&A, vector &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 vector BigInt_sub(vector &A, vector &B) { vector C; for (int i = 0, t = 0; i < A.size(); i ++ ) { t = A[i] - t; if (i < B.size()) t -= B[i]; C.push_back((t + 10) % 10); // 综合了两种情况 if (t < 0) t = 1; else t = 0; } // 由于输出的位数是与 A 相同的，可能存在前导 0 ，因此需要循环判断一下删除前导 0 while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; }
【高精度乘法】
vectorBigInt_mul(vector &A, int b) { vector C; int t = 0; for (int i = 0; i < A.size() || t; i ++ ) { if (i < A.size()) t += A[i] * b; C.push_back(t % 10); t /= 10; } while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; }
【高精度除法】
vector3. 应用：模板题 （1）高精度加法BigInt_div(vector &A, int b, int &r) { vector 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; }
AcWing 791. 高精度加法
【不压位 - C++代码】
#include#include using namespace std; vector BigInt_add(vector &A, vector &B) { if (A.size() < B.size()) return BigInt_add(B, A); vector C; int t = 0; for (int i = 0; i < A.size(); i ++ ) { t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(t); return C; } int main() { string a, b; vector A, B; cin >> 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'); auto C = BigInt_add(A, B); for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i]; cout << endl; return 0; }
【压 9 位 - C++代码】
#include#include using namespace std; const int base = 1000000000; vector BigInt_add(vector &A, vector &B) { if (A.size() < B.size()) return BigInt_add(B, A); vector C; int t = 0; for (int i = 0; i < A.size(); i ++ ) { t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % base); t /= base; } if (t) C.push_back(t); return C; } int main() { string a, b; vector A, B; cin >> a >> b; for (int i = a.size() - 1, s = 0, j = 0, t = 1; i >= 0; i -- ) { s += (a[i] - '0') * t; j ++, t *= 10; if (j == 9 || i == 0) { A.push_back(s); s = j = 0; t = 1; } } for (int i = b.size() - 1, s = 0, j = 0, t = 1; i >= 0; i -- ) { s += (b[i] - '0') * t; j ++, t *= 10; if (j == 9 || i == 0) { B.push_back(s); s = j = 0; t = 1; } } auto C = BigInt_add(A, B); cout << C.back(); for (int i = C.size() - 2; i >= 0; i -- ) printf("%09d", C[i]); cout << endl; return 0; }
（2）高精度减法
AcWing 792. 高精度减法
【C++代码】
#include#include using namespace std; bool cmp(vector &A, vector &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; } vector BigInt_sub(vector &A, vector &B) { vector C; for (int i = 0, t = 0; i < A.size(); i ++ ) { t = A[i] - t; if (i < B.size()) t -= B[i]; C.push_back((t + 10) % 10); if (t < 0) t = 1; else t = 0; } while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main() { string a, b; vector A, B; cin >> 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 C; if (cmp(A, B)) C = BigInt_sub(A, B); else C = BigInt_sub(B, A), cout << '-'; for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i]; cout << endl; return 0; }
（3）高精度乘法
AcWing 793. 高精度乘法
【C++代码】
#include#include using namespace std; vector BigInt_mul(vector &A, int b) { vector C; int t = 0; for (int i = 0; i < A.size() || t; i ++ ) { if (i < A.size()) t += A[i] * b; C.push_back(t % 10); t /= 10; } while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main() { string a; int b; cin >> a >> b; vector A; for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); auto C = BigInt_mul(A, b); for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]); return 0; }
（4）高精度除法
AcWing 794. 高精度除法
【C++代码】
#include#include #include using namespace std; vector BigInt_div(vector &A, int b, int &r) { vector 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; vector A; int B; cin >> a >> B; for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); int r; auto C = BigInt_div(A, B, r); for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i]; cout << endl << r << endl; return 0; }
