一、高精度加法：
算法模板：
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); return C; }
例题：
给定两个正整数（不含前导 00），计算它们的和。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的和。
数据范围
1≤整数长度≤1000001≤整数长度≤100000
输入样例：
12 23
输出样例：
35
#include<iostream> #include<vector> using namespace std; 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); return C; } int main() { string a,b; vector<int> A,B; //a=456342420298425631002819049046,b=42568245372799024844654500802 cin>>a>>b; //A=[6,4,0,9,4,0,9,1,8,2,0,0,1,3,6,5,2,4,8,9,2,0,2,4,2,4,3,6,5,4,4] for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0'); //B=[2,0,8,0,0,5,4,5,6,4,4,8,4,,2,0,9,9,7,2,7,3,5,4,2,8,6,5,2,4] for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0'); //C=[8,4,8,9,4,5,3,7,4,7,4,8,5,5,6,4,2,2,1,7,6,5,6,6,0,1,9,8,9,4] //C=[4,9,8,9,1,0,6,6,5,6,7,1,2,2,4,6,5,5,8,4,7,4,7,3,5,4,9,8,4,8] auto C=add(A,B); for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]); }
二、高精度减法：
思路：
和高精度加法差不多，值得注意的是
减法的借位处理
相减为负数的处理
前导0的处理
相减后t的处理 ，把 t >=0 和 t < 0 用一个式子来表示 t = (t + 10) % 10
算法模板：
A与B的判断：
bool cmp(vector<int>& A, vector<int> &B) { if(A.size() != B.size()) return A.size() > B.size(); //直接ruturn 了就不用else for(int i = A.size(); i >= 0; i--) if(A[i] != B[i]) return A[i] > B[i]; return true; }
减法模板：
vector<int> sub(vector<int>& A,vector<int>& B) { vector<int>C; int t=0;//退位 for(int i=0;i<A.size();i++) { t=A[i]-t; if(i<B.size())t-=B[i]; C.push_back((t+10)%10); // 将t>0输出t和t<0输出t+10俩种情况合而为1 if(t<0)t=1; else t=0; } while(C.size() > 1 && C.back() == 0) C.pop_back(); //去掉前导0 return C; }
例题：
给定两个正整数（不含前导 00），计算它们的差，计算结果可能为负数。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的差。
数据范围
1≤整数长度≤10^5
输入样例：
32 11
输出样例：
21
#include<iostream> #include<vector> using namespace std; //判断是否有A>=B bool cmp(vector<int>&A,vector<int>&B) { if(A.size()!=B.size())return A.size()>B.size();//直接ruturn 了就不用else for(int i=A.size();i>=0;i--) { if(A[i]!=B[i]) return A[i]>B[i]; } return true; } vector<int> sub(vector<int>& A,vector<int>& B) { vector<int>C; int t=0;//退位 for(int i=0;i<A.size();i++) { t=A[i]-t; if(i<B.size())t-=B[i]; C.push_back((t+10)%10); // 将t>0输出t和t<0输出t+10俩种情况合而为1 if(t<0)t=1; 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'); for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0'); if(cmp(A,B)) { auto C=sub(A,B); for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]); return 0; } else { auto C=sub(B,A); cout<<"-"; for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]); return 0; } return 0; }
三、高精度乘法
乘法模板：
vector<int>mul(vector<int>A,int b) { int t=0; vector<int>C; for(int i=0;i<A.size();i++) { if(i<A.size())t+=A[i]*b;// t + A[i] * b = 7218 C.push_back(t%10);// 只取个位 8 t/=10; // 721 看作进位 } while (t)// 处理最后剩余的 t { C.push_back(t % 10); t /= 10; } //去掉前导0 while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; }
例题：
给定两个非负整数（不含前导 00） A 和 B，请你计算 A×B 的值。
输入格式
共两行，第一行包含整数 A，第二行包含整数 B。
输出格式
共一行，包含 A×B 的值。
数据范围
1≤A的长度≤100000
0≤B≤100000
输入样例：
2 3
输出样例：
6
#include<iostream> #include<vector> using namespace std; vector<int>mul(vector<int>A,int b) { int t=0; vector<int>C; //与高精度加法思路相似 for(int i=0;i<A.size();i++) { if(i<A.size())t+=A[i]*b;// t + A[i] * b = 7218 C.push_back(t%10);// 只取个位 8 t/=10; // 721 看作进位 } while (t)// 处理最后剩余的 t { C.push_back(t % 10); t /= 10; } //去掉前导0 while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main() { string a; int b; vector<int>A; cin>>a>>b; for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0'); auto C=mul(A,b); for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]); return 0; }
四、高精度除法
除法模板：
vector<int> div(vector<int> &A,int B,int &r) { vector<int> C; for(int i=0;i<A.size();i++) { r=r*10+A[i]; C.push_back(r/B); r=r%B; } reverse(C.begin(),C.end()); while(C.size()>1&&C.back()==0) C.pop_back(); return C; }
例题：
给定两个非负整数（不含前导 00） A，B请你计算 A/B的商和余数。
输入格式
共两行，第一行包含整数 A，第二行包含整数 B。
输出格式
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围
1≤A的长度≤100000
1≤B≤10000
B 一定不为 0
输入样例：
7 2
输出样例：
3 1
#include<iostream> #include<vector> #include<algorithm> using namespace std; //int r=0; vector<int> div(vector<int> &A,int B,int &r) {//r传入r的地址，便于直接对余数r进行修改 vector<int> C; for(int i=0;i<A.size();i++) {//对A从最高位开始处理 r=r*10+A[i];//将上次的余数*10在加上当前位的数字，便是该位需要除的被除数 C.push_back(r/B);//所得即为商在这一位的数字 r=r%B; } //由于在除法运算中，高位到低位运算，因此C的前导零都在vector的前面而不是尾部，vector只有删除最后一个数字pop_back是常数复杂度，而对于删除第一位没有相应的库函数可以使用，而且删除第一位，其余位也要前移， //因此我们将C翻转，这样0就位于数组尾部，可以使用pop函数删除前导0 reverse(C.begin(),C.end()); while(C.size()>1&&C.back()==0) C.pop_back(); return C; } int main() { string a; int B,r=0; //代表余数 cin>>a>>B; vector<int> A; for(int i=0;i<a.size();i++) A.push_back(a[i]-'0');//注意这次的A是由高为传输至低位，由于 在除法的手算过程中，发现从高位进行处理 //for(int i=0;i<A.size();i++) cout<<A[i]; //cout<<B; auto C = div(A,B,r); for(int i=C.size()-1;i>=0;i--) cout<<C[i];//将C从最高位传给最低位 cout<<endl<<r;//输出余数 cout<<endl; return 0; }
