高精度极速版（总结）
省流: 最后结果都是从尾打印
高精度加法: 分别判断a, b长度再加
高精度减法: 判断大减小cmp，判断b长度再减，删前导0
高精度乘法: 判0，删没用到的前导0（低精度不用删）
高精度除法: 判0，翻转再删前导0
01_高精度加法 high-precision_addition
（1）用 string
#include <iostream>
#include <algorithm>
using namespace std;
string add(string a, string b) {
string sum;
int t = 0;
int i = a.size() - 1, j = b.size() - 1; // 从个位开始逐位倒着加
/*
什么时候加完 -> 注意判 0:
两数长度可能不同: i, j 判 0
最高位也可能进位: t 判 0
*/
for (; i >= 0 || j >= 0 || t > 0; i--, j--) {
if (i >= 0) t += a[i] - '0';
if (j >= 0) t += b[j] - '0';
sum += (t % 10) + '0';
t /= 10;
}
reverse(sum.begin(), sum.end());
return sum;
}
int main() {
string a, b;
cin >> a >> b;
cout << add(a, b) << endl;
return 0;
}
（2）用 vector
#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int> &a, vector<int> &b) {
vector<int> s;
int t = 0; // 进位
for (int i = 0; i < a.size() || i < b.size() || t > 0; i++) {
if (i < a.size()) t += a[i];
if (i < b.size()) t += b[i];
s.push_back(t % 10);
t /= 10;
}
return s;
}
int main() {
string A, B;
cin >> A >> B;
vector<int> 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 s = add(a, b);
for (int i = s.size() - 1; i >= 0; i--) cout << s[i]; // 倒着存的所以倒着输出
return 0;
}
02_高精度减法 high-precision_subtraction
#include <iostream>
#include <vector>
using namespace std;
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;
}
vector<int> sub(vector<int> &a, vector<int> &b) {
vector<int> s;
int t = 0; // 借位
for (int i = 0; i < a.size(); i++) {
/*
学过减法易得:
a[i] >= b[i]: a[i] - t - b[i]
a[i] < b[i]: a[i] - t - b[i] + 10
为了把这两种情况合一起，把重复的部分存到 t 里:
t = a[i] - t - b[i] (作右值的 t 是上一位的借位)
易知 t 肯定是个位数:
t >= 0: 不用借位，已是正确结果，+10 再 %10 没有影响 (妙啊！)
t < 0: 需要借位，+10 得到正确结果，再 %10 没有影响 (妙啊！)
*/
t = a[i] - t;
if (i < b.size()) t -= b[i]; // 因为 b 的长度还要判断所以把上面说的重复的部分分开写了
s.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
/*
删除前导0，注意要留一位
例: 999 - 999 = 000，删掉多余的0
*/
while (s.size() > 1 && s.back() == 0) s.pop_back();
return s;
}
int main() {
string A, B;
cin >> A >> B;
vector<int> 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> s;
if (!cmp(a, b)) s = sub(b, a), s.back() *= -1;
else s = sub(a, b);
for (int i = s.size() - 1; i >= 0; i--) cout << s[i]; // 倒着存的所以倒着输出
return 0;
}
03_高精度乘法 high-precision_multiplication
（1）高精度 * 低精度
#include <iostream>
#include <vector>
using namespace std;
vector<int> muti(vector<int> &a, int &b) {
vector<int> s;
int t = 0; // 进位
/*
学过乘法易知:
s[i]: (a[i] * b + t) % 10
t : (a[i] * b + t) / 10
不用删除前导0
*/
for (int i = 0; i < a.size() || t > 0; i++) {
if (i < a.size()) t += a[i] * b;
s.push_back(t % 10);
t /= 10;
}
return s;
}
int main() {
string A;
int b;
cin >> A >> b;
if (A == "0" || b == 0) cout << 0 << endl; // 先筛0, 减少开销
else {
vector<int> a;
for (int i = A.size() - 1; i >= 0; i--) a.push_back(A[i] - '0');
auto s = muti(a, b);
for (int i = s.size() - 1; i >= 0; i--) cout << s[i];
}
return 0;
}
（2）高精度 * 高精度
#include <iostream>
#include <vector>
using namespace std;
vector<int> muti(vector<int> &a, vector<int> &b) {
/*
乘法的结果最多不会超过两数长度之和;
填 0: 方便删除多余的前导数，且避免脏数据
*/
vector<int> s(a.size() + b.size(), 0);
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < b.size(); j++) {
s[i + j] += a[i] * b[j]; // 就是乘法算式，把每一列加起来
}
}
/*
先让下一位把进位加上，再算当下位的结果;
易知最后一位 s[s.size() - 1] 不会再产生进位，所以 i 遍历到倒数第二位就行了
如果用 t 作进位:
int t = 0;
for (int i = 0; i < s.size(); i++) {
s[i] += t;
t = s[i] / 10;
s[i] %= 10;
}
*/
for (int i = 0; i < s.size() - 1; i++) {
s[i + 1] += s[i] / 10;
s[i] %= 10;
}
// 删除前导0: 最前面已经筛过0了，结果不可能是0，所以不用判断长度
while (s.back() == 0) s.pop_back();
return s;
}
int main() {
string A, B;
cin >> A >> B;
if (A == "0" || B == "0") cout << 0 << endl; // 先筛0, 减少开销
else {
vector<int> 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 s = muti(a, b);
for (int i = s.size() - 1; i >= 0; i--) cout << s[i];
}
return 0;
}
04_高精度除法 high-precision_division
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> divi(vector<int> &a, int &b, int &r) {
vector<int> s;
for (int i = a.size() - 1; i >= 0; i--) {
r = r * 10 + a[i]; // 上一位的余数*10 + 当下位
s.push_back(r / b);
r %= b; // 余数
}
reverse(s.begin(), s.end()); // 删前导0得从最后删所以翻转一下
while (s.size() > 1 && s.back() == 0) s.pop_back(); // 删除前导0: 前几位可能商多余的0
return s;
}
int main() {
string A;
int b;
cin >> A >> b;
if (A == "0" || b == 0) cout << 0 << endl << 0 << endl;
else {
vector<int> a;
// 除法是正着算，但是为了和加减乘保持统一所以还是倒着存了
for (int i = A.size() - 1; i >= 0; i--) a.push_back(A[i] - '0');
int r = 0; // 余数
auto s = divi(a, b, r);
// 删前导0的时候翻转了所以还是倒着输出
for (int i = s.size() - 1; i >= 0; i--) cout << s[i];
cout << endl << r << endl;
}
return 0;
}
