高精度加法
AcWing.791高精度加法
# include <iostream>
# include <string>
# 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 = t / 10;
}
if(t) C.push_back(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‘);
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];
return 0;
}
高精度减法
AcWing.792高精度减法
# include <iostream>
# include <string>
# include <vector>
using namespace std;
bool cmp(vector<int>& A, vector<int>& B){
if(A.size() != B.size()) return A.size() > B.size(); // A和B长度不相等
for(int i = A.size() - 1; i >= 0; i --){ //A和B长度相等
if(A[i] != B[i]) return A[i] > B[i];
}
return true; //A和B一样
}
vector<int> sub(vector<int>& A, vector<int>& B){ //规定 A 比 B 大
vector<int> C;
int t = 0; //借位
int res; // res = A[i] - B[i] - t
for(int i = 0; i < A.size(); i ++){
res = A[i] - t;
if(i < B.size()) res -= B[i]; //如果B有数,则减去B[i]
if(res >= 0){ //不用借位
C.push_back(res);
t = 0;
}
else{ //需要借位
C.push_back(res + 10);
t = 1;
}
}
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)){
vector<int> C = sub(A, B);
for(int i = C.size() - 1; i >= 0; i --) cout << C[i];
}else{
vector<int> C = sub(B, A);
cout << "-";
for(int i = C.size() - 1; i >= 0; i --) cout << C[i];
}
return 0;
}
高精度乘法(大精度×小精度)
AcWing.793高精度乘法
# include <iostream>
# include <string>
# include <vector>
using namespace std;
vector<int> mul(vector<int>& A, int b){
vector<int> C;
int res, t = 0;
for(int i = 0; i < A.size(); i ++){
res = A[i] * b + t;
C.push_back(res % 10);
t = res / 10;
}
if(t) C.push_back(t);
while(C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main(){
string a;
vector<int> A;
int b;
cin >> a >> b;
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];
return 0;
}
高精度除法(高精度除以低精度)
AcWing.794高精度除法
# include <iostream>
# include <string>
# include <vector>
# include <algorithm>
using namespace std;
vector<int> div(vector<int>& A, int b, int& r){
vector<int> C; //商
r = 0; //余数
int res;
for(int i = A.size() - 1; i >= 0; i --){
res = r * 10 + A[i];
C.push_back(res / b);
r = res % b;
}
reverse(C.begin(), C.end());
while(C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main(){
string a;
int b, r;
vector<int> A;
cin >> a >> b;
for(int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - ‘0‘);
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;
}
高精度算法