高精度运算（加减乘除 模板 & 例题）：当long long也存储不下的时候……
高精度运算（加减乘除 模板 & 例题）：当long long也存储不下的时候……
早上好啊，大佬们，上次的二分不知道大家学得怎么样了，今天这个高精度总归还是来了，对付一些特殊的题目的时候非用不可。
但是，本期Python 和 java 朋友们就不用看，C/C++的朋友们看过来咯~
众所周知，C/C++的整数存储是有上限的，所以题目有时候就会为难我们，让我们运算两个很大的数，那我们肯定不能空着啊，这时候就需要高精度算法，加减乘除都有，大家好好看，好好学~
一、高精度，这名字真厉害
小白兔：“老师，long long已经存不下啦！”
老师：“不是吧，不是吧~人机都知道这里要用高精度”
这时就该高精度算法闪亮登场了——就像给计算机一本无限页的草稿本，让它能把数字拆成一个个字符，用最原始的竖式计算法慢慢折腾。这波操作堪称人类对计算机的"降维打击"：你CPU不是快吗？我偏要让你用最笨的方法算！
二、高精度三部曲
（一）、大整数存储
数字变形记：把"12345"变成[5 , 4 , 3 , 2 , 1]
（别问为什么倒着存，就像问为什么程序员计数从0开始——传统艺能罢了）
因为加法运算有进位，在数组最前端加一位，相当于把整个数组往后移一位；而在最后就一个push_back就行了。
（二）、编写对应函数
对每一位进行运算，得到答案数组
● 高精度加法、高精度减法
● 高精度乘法、高精度除法
（三）、用循环输出答案
这个就像如鱼得水，在所有步骤里面这个太简单了。
三、代码模板
高精度加法
我们通过一个例题来写这个代码模板，
例题
高精度加法
题目描述
给定两个整数 a和b，请你求出这两个整数的和。
输入描述
输入两个正整数 a,b，a 和 b 都不超过 100 位。
输出描述
输出
a+b 。
输入输出样例
示例
输入
1234567890123456789
9876543210987654321
输出
11111111101111111110
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
// 第二步、C = A + B大整数加法
vector<int> add(vector<int> &A, vector<int> &B) //取地址是为了加快运行速度
{
vector<int> C;
int t = 0;
for(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); //如果最高位不为 0，要添加上 t ， 此时t 固定为 1。
return C;
}
int main()
{
// 请在此输入您的代码
string a, b; //用来获取两个整数
vector<int> A, B;
cin >> a >> b;
//第一步、大整数存储
for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0'); //我们将整数倒着存进数组
//也就是 将a 存储到 A 中。
for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0'); //i - '0' 是将字符型转换成整数型
//同理
auto C = add(A, B); //auto 作用是自动判断数据类型，然后定义 i 的数据类型
//输出C
for(int i = C.size() - 1; i >= 0; i--) cout << C[i];
return 0;
}
高精度减法
例题
高精度减法
题目描述
高精度减法。
输入格式
两个整数 a,b（第二个可能比第一个大）。
输出格式
结果（是负数要输出负号）。
输入输出样例
输入
2
1
输出
1
说明/提示
20% 数据 a,b 在 long long 范围内；
100% 数据 0<a,b≤1010086
说明
- 在计算减法时，大数减小数 为 正；小数减大数 为 负。所以先判断A 和 B哪个数大。
- 该位的数 = A[ i ] - 借位 - B[ i ]
- 如果有借位，该数要 + 10 。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
bool cmp(vector<int> &A, vector<int> &B) //用来判断 A 和 B 的大小关系
{
// 我们返回 true 为 A 大，false 为 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; //避免两个数一样大，在循环里卡死，随便返回true 和 false是一样的
}
// 第二步、C = A - B大整数减法
vector<int> sub(vector<int> &A, vector<int> &B) //取地址是为了加快运行速度
{
vector<int> 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; //如果 t < 0，则是借位来的，需要 + 10；如果 t > 0，就不变。
else t = 0;
}
while (C.size() > 1 && C.back() == 0) C.pop_back(); //如果最高位是 0 要去掉
return C;
}
int main()
{
// 请在此输入您的代码
string a, b; //用来获取两个整数
vector<int> A, B;
cin >> a >> b;
//第一步、大整数存储
for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0'); //我们将整数倒着存进数组
//也就是 将a 存储到 A 中。
for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0'); //i - '0' 是将字符型转换成整数型
//同理
//因为 A 和 B 的大小会影响整体的计算，所以我们保证 大数减小数 能让计算变简单。
if (cmp(A, B)){
auto C = sub(A, B); //auto 作用是自动判断数据类型，然后定义 i 的数据类型
//输出C
for(int i = C.size() - 1; i >= 0; i--) cout << C[i];
}
else{
auto C = sub(B, A); //auto 作用是自动判断数据类型，然后定义 i 的数据类型
//输出C
cout << '-'; //因为是 A - B 所以这里要多 - 号
for(int i = C.size() - 1; i >= 0; i--) cout << C[i];
}
return 0;
}
高精度乘法
例题
高精度乘法
题目描述
给定两个位数不超过100位的正整数，求它们的乘积。
输入描述
输入文件中包含多个测试数据。每个测试数据占两行，分别为一个正整数，每个正整数的位数不超过100位。输入数据一直到文件尾。
输出描述
对每个测试数据，输出其中两个正整数的乘积。
样例输入
981567
32976201
123456789
987654321
copy
样例输出
32368350686967
121932631112635269
思路
将两个大整数的乘法转换成 —— 一个大整数 和 一位数的乘法，然后相加。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
// 第二步、C = A * B大整数乘法
vector<int> mul(vector<int> &A, vector<int> &B)
{
vector<int> C(A.size() + B.size() + 10, 0); //初始化长度，并且都置为 0
for(int i = 0; i < A.size(); i ++)
for(int j = 0; j < B.size(); j ++)
C[i + j] += A[i] * B[j]; //该位直接存储相乘的结果
//这里有个小巧思，就是当乘第二个数时需要移动一位，而移动的位数和i值是相同的，所以写成了 C[i + j]
for(int i = 0; i < C.size() - 1; i ++)
{
C[i + 1] += C[i] / 10; //和前面加法的写法是一样的。
C[i] %= 10;
}
while(!C.back() && C.size() > 1) C.pop_back();
return C;
}
int main()
{
// 请在此输入您的代码
string a, b; //用来获取两个整数
while(cin >> a >> b){
vector<int> A, B; //一定要放在循环里进行重置，否则会出错的
//第一步、大整数存储
for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0'); //我们将整数倒着存进数组
//也就是 将a 存储到 A 中。
for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0'); //i - '0' 是将字符型转换成整数型
//同理
auto C = mul(A, B); //auto 作用是自动判断数据类型，然后定义 i 的数据类型
//输出C
for(int i = C.size() - 1; i >= 0; i--) cout << C[i];
cout << "\n";
}
return 0;
}
高精度除法
例题
高精度除法
题目描述
输入两个整数 a,b，输出它们的商。
输入格式
两行，第一行是被除数，第二行是除数。
输出格式
一行，商的整数部分。
输入输出样例
输入
10
2
输出
5
说明/提示
0≤a≤105000，1≤b≤109。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
// 第二步、C = A / B大整数除法
vector<int> div(vector<int> &A, long long b) //取地址是为了加快运行速度
{
vector<int> C;
long long 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(); //如果最高位是 0 要去掉
return C;
}
int main()
{
// 请在此输入您的代码
string a; //用来获取两个整数
long long b;
vector<int> A;
cin >> a >> b;
//第一步、大整数存储
for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0'); //我们将整数倒着存进数组
//也就是 将a 存储到 A 中。
//因为 高精度除法一般除数都是一个比较小的数，所以直接用就行了
auto C = div(A, b); //auto 作用是自动判断数据类型，然后定义 i 的数据类型
//输出C
for(int i = C.size() - 1; i >= 0; i--) cout << C[i];
return 0;
}
总结
赠言：下次面试被问到高精度时，请优雅地扶眼镜说：“这不过是把小学数学教给计算机罢了，毕竟…人工智能要从娃娃抓起？”（手动狗头）
今天这一期就到这了，如果大家觉得有用，希望多多点赞收藏，也别忘了点点关注~