关于高精度：高精度就是计算结果位数非常多，一般的数字整型无法正常显示，java和Python无需考虑，语法自带即可完成高精度处理
高精度加法
高精度加法就是用数组来模拟人的加法过程，先加个位，然后十位、百位、千位，每一位都要考虑上一位的进位，由于最后可能还存在一位进位，因此用大端模式存储（即数字的高位在数组的高位，数字的低位在数组的低位，即nums[0]是个位）可以利用数组的push_back()而无需搬移整个数组来在最前面加一位。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
vector<int> add(vector<int>& A, vector<int>& B) {
if (A.size() < B.size()) return add(B, A);
vector<int> ans;
// i是位数，由低到高分别是个位->最高位，t是进位
int t = 0;
for (int i = 0; i < A.size(); ++i) {
int cur = A[i] + (i < B.size() ? B[i] : 0) + t;
ans.push_back(cur % 10);
t = cur / 10;
}
if (t) ans.push_back(t);
return ans;
}
|
高精度减法
与高精度加法类似，也是从低位减起，不够减需要向高位借位，因此一定要用大的减小的，小的减大的则反过来减然后补负号
用cmp来判断A和B的大小，sub用来做减法，要求大的减小的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
// 判断A大于等于B
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 true;
else if (A[i] < B[i]) return false;
else continue;
}
return true;
}
vector<int> sub(vector<int>& A, vector<int>& B) {
vector<int> ans;
// 这里就已经保证了A是大于等于B的
for (int i = 0, t = 0; i < A.size(); ++i) {
int cur = A[i] - (i < B.size() ? B[i] : 0) - t;
if (cur >= 0) {
t = 0;
} else {
cur += 10;
t = 1;
}
ans.push_back(cur);
}
while (ans.size() > 1 && ans.back() == 0) ans.pop_back();
return ans;
}
|
高精度乘法
和加法非常像，对于高精度数字A和普通数字B，A * B的结果是A中每一位与B相乘的结果相加，注意进位即可
1
2
3
4
5
6
7
8
9
10
|
vector<int> mul(vector<int>& A, int b) {
if (b == 0) return {0};
vector<int> ans;
for (int i = 0, t = 0; i < A.size() || t; ++i) {
if (i < A.size()) t += A[i] * b;
ans.push_back(t % 10);
t /= 10;
}
return ans;
}
|
高精度除法
模拟除法，与上述三种的不同在于，除法要先从高位开始除，不够除就是零，✖️10加上下一位继续除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
vector<int> div(vector<int>& A, int b, int& r) {
// A 除 b，r是余数
if (b == 0) return {};
r = 0;
vector<int> ans;
// 这里依旧是高位表示的是高位
for (int i = A.size() - 1; i >= 0; --i) {
r = r * 10 + A[i];
ans.push_back(r / b);
r = r % b;
}
reverse(ans.begin(), ans.end());
while (ans.size() > 1 && ans.back() == 0) ans.pop_back();
return ans;
}
|
Sugar