一、高精度
当一个数很大，大到 int 无法存下时，我们可以考虑用数组来进行存储，即数组中一个位置存放一位数。
但是对于数组而言，一个数顺序存入数组后，对其相加减是很简单的。但是当需要进位时，还是很麻烦的，因为要将整个数组全都往后移动一位，将最高位的进位位置空出来，这个操作的时间复杂度是 O(n) 。
不过，我们有一种方法可以很好的解决进位这个问题，就是将这个数的个位数存至数组中的第一位（即 a[0] ），最高位存入数组的最后一位（a [n-1]）。这样在处理进位时可以直接在数组的最后一位添加即可。最后在输出时逆序输出即可。
1、高精度加法
举个例子：求 9724 + 377 的和。
将两个数分别存入 a 数组和 b 数组中，如下所示：
这样，运算过程就很简单了。将第一个位置进行相加，如果 > 9 就要进一位（这一步可以利用取模来实现）。再将第二个位置的数相加，同时加上前一位的进位，再判断是否 > 9 。以此类推便可求出最终结果。
（1）高精度加法模板
🔺记忆！
// C = A + B, A >= 0, B >= 0 vector<int> add(vector<int> &a,vector<int> &b){ //c为答案 vector<int> c; //t为进位 int t=0; for(int i=0;i<a.size()||i<b.size();i++){ //不超过a的范围添加a[i] if(i<a.size())t+=a[i]; //不超过b的范围添加b[i] if(i<b.size())t+=b[i]; //取当前位的答案 c.push_back(t%10); //是否进位 t/=10; } //如果t!=0的话向后添加1 if(t)c.push_back(1); return c; }
（2）注意事项
a. 其他写法
如果要处理长度不一致的情况，该怎么做？
可以在循环外先使用条件判断语句来处理这种情况。
可以先判断两个数组的大小，这样在写循环时可以省略一些步骤，但从代码可读性上来讲，还是上面的写法更好理解。
vector<int> add(vector<int> &A, vector<int> &B) { if (A.size() < B.size()) return add(B, A); vector<int> C; int t = 0; for (int i = 0; i < A.size(); i ++ ) { t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(t); return C; }
b. 前导 0
如何处理前导 0？
这里所给两个整数不含前导 0，则不需要考虑。处理前导 0 的做法，下面会有详细介绍。
c. 进位
最后需要判断进位是否为 0，如果不为 0，那么不要忘记进 1。为什么是 1，而不可能是其他数字呢？是因为这里是加法，最多只有可能是 9+9，然后再加上一个进位 1，为 19，不会超过这个数，所以之能是 1。
d. 输入输出
需要注意输入时，是从字符串的末尾（即低位： a.size()-1 / b.size()-1 ）往前（即 a[0] / b[0] ）方向 push_back 输入，那么在 A / B 数组里就会反过来，从低位数在高位下标，高位数在低位下标——>低位数在低位下标，高位数在高位下标，符合我们想要的效果。
e. vector
为什么这里要使用 vector 呢？
- vector 是一个动态数组，可以根据需要动态地分配和释放内存，灵活性较高。在这个场景中，数字相加的结果的位数是不确定的，使用 vector 可以方便地根据实际结果的位数来动态扩展数组的大小。
- vector 提供了丰富的操作函数和方法，如 push_back 用于给末尾添加元素，size 用于获取向量长度，以及通过索引访问元素等。这些方法使得在遍历和操作相加结果的过程中更加方便和高效。
- vector 支持直接返回，可以将结果直接返回给调用者，而不需要手动管理内存或进行额外的拷贝操作。这样可以简化代码，并提高代码的可读性和可维护性。
（3）练习
2、高精度减法
减法与加法类似，具体区别有以下有两点：
- 是大的数减小的数还是小的数减大的数，这两种情况的共同点在于它们相减后的绝对值是一样的，所以我们只需要在运算前来判断数的大小即可。
- 也有可能两个数相等或者高位数值相等，那么在相减的过程中会产生 0 ，并且这个 0 是在高位的，在输出时会输出 0 ，那么得要去除这个 0 。若是要求出产生 0 的位置，这个步骤是相对繁琐的。这个时候用数组倒序存数的又一大优势来了，可以直接利用 pop_back() 去除最后的元素（即最高位的元素）。
⚪高精度比大小 （cmp函数）
🔺记忆！
//高精度比大小 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; }
（1）高精度减法模板
🔺记忆！
// C = A - B, 满足A >= B, A >= 0, B >= 0 vector<int> sub(vector<int> &A, vector<int> &B) { //答案 vector<int> C; //遍历最大的数 for (int i = 0, t = 0; i < A.size(); i ++ ) { //t为进位 t = A[i] - t; //不超过B的范围t=A[i]-B[i]-t; if (i < B.size()) t -= B[i]; //合二为一，取当前位的答案 C.push_back((t + 10) % 10); //t<0则t=1 if (t < 0) t = 1; //t>=0则t=0 else t = 0; } //去除前导零 while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; }
（2）注意事项
a. sub 函数里的 for 循环
因为已经提前确定了函数里的 A.size() >= B.size(); 所以在 for 循环中省略了一个条件判断。
b. 去除前导 0
当数组里的有效数字 > 1 时（答案结果只有一个数字 0，就不需要去除了），且数组末尾（即 back() ）为 0 时，利用 while 循环 pop_back 掉这些前导 0。
c. (t + 10)%10
这里会分两种情况：
- t > 0：(t + 10)%10 = t;
- t < 0：t < 0 需要借 1，得到 t+10，由于 t 是负个位数，所以 (t+10)%10 结果为正个位数。
通过 (t + 10)%10 巧妙地将两种情况结合起来。
（3）练习
3、高精度乘法
（1）高精度乘低精度
1、高精度乘低精度模板
🔺记忆！
// C = A * b, A >= 0, b >= 0 vector<int> mul(vector<int> &A, int b) { //类似于高精度加法 vector<int> C; //t为进位 int t = 0; for (int i = 0; i < A.size() || t; i ++ ) { //不超过A的范围t=t+A[i]*b if (i < A.size()) t += A[i] * b; //取当前位的答案 C.push_back(t % 10); //进位 t /= 10; } //去除前导零 while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; }
2、注意事项
a. 循环条件
在遍历数组 A 的每一位时，需要考虑两个条件：
- 数组A的长度，即 A.size();
- 进位的情况，即当进位不为 0 时，还需要继续进行运算。
b. 去除前导 0
与高精度减法一致，当数组里的有效数字 > 1 时（答案结果只有一个数字 0，就不需要去除了），且数组末尾（即 back() ）为 0 时，利用 while 循环 pop_back 掉这些前导 0。这里的去除前导 0 是用来考虑 b 是否等于 0 这种情况的，其他情况不会出现前导 0。
（2）高精度乘高精度
1、高精度乘高精度模板
🔺记忆！
vector<int> mul(vector<int> &A, vector<int> &B) { vector<int> C(A.size() + B.size()); // 初始化为 0，C的size可以大一点 for (int i = 0; i < A.size(); i++) for (int j = 0; j < B.size(); j++) C[i + j] += A[i] * B[j]; for (int i = 0,t = 0; i < C.size(); i++) { // i = C.size() - 1时 t 一定小于 10 t += C[i]; C[i] = t % 10; t /= 10; } while (C.size() > 1 && C.back() == 0) C.pop_back(); // 必须要去前导 0，因为最高位很可能是 0 return C; }
2、注意事项
a. 进位
为什么 i = C.size() - 1 时，t 一定小于 10？
由于每一位的计算都是将乘法结果加到当前位上，并累积进位值 t，所以在当 i = C.size() - 1时，t 的最大值为乘法结果最高位的数字与之前的进位相加，而乘法结果的每一位数字都 <= 9，进位值 t 也 <= 9。因此，当 i = C.size() - 1 时，进位值 t 一定 < 10。
b. 去除前导 0
与前面一致，当数组里的有效数字 > 1 时（答案结果只有一个数字 0，就不需要去除了），且数组末尾（即 back() ）为 0 时，利用 while 循环 pop_back 掉这些前导 0。
（3）练习
4、高精度除法
（1）高精度除低精度
1、高精度除低精度模板
🔺记忆！
// A / b = C ... r, A >= 0, b > 0 vector<int> div(vector<int> &A, int b, int &r)//高精度A，低精度b，余数r { vector<int> C;//答案 r = 0; for (int i = A.size() - 1; i >= 0; i -- ) { r = r * 10 + A[i];//补全r>=b C.push_back(r / b);//取当前位的答案 r %= b;//r%b为下一次计算 } reverse(C.begin(), C.end());//倒序为答案 while (C.size() > 1 && C.back() == 0) C.pop_back();//去除前导零 return C; }
2、注意事项
a. 去除前导 0
与前面一致，当数组里的有效数字 > 1 时（答案结果只有一个数字 0，就不需要去除了），且数组末尾（即 back() ）为 0 时，利用 while 循环 pop_back 掉这些前导 0。
b. 输出顺序
这里通过 reverse 函数将答案倒序为正常顺序。一道题目可能会涉及多种运算，顺序统一更容易处理。
c. 余数
首先将余数 r 初始化为 0，然后从被除数的最高位开始逐位进行除法运算，计算当前位的商并将其添加到结果数组 C 中。具体地，每次对余数 r 进行一次进位运算，将其乘以 10 并加上当前位的数字，得到除数后将其除以 b（低精度除法），即可得到当前位的商，余数则更新为当前余数对除数取模的结果，作为下一次迭代的余数。
d. 除数
注意在 div 函数中不要将 b 习惯性写成 10。
（2）高精度除高精度
⚪高精度比大小 （cmp函数）
🔺记忆！
//高精度比大小 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; }
1、高精度除高精度模板
🔺记忆！
vector<int> div(vector<int> &A, vector<int> &B, vector<int> &r) { vector<int> C; if (!cmp(A, B)) { C.push_back(0); r.assign(A.begin(), A.end()); return C; } int j = B.size(); r.assign(A.end() - j, A.end()); while (j <= A.size()) { int k = 0; while (cmp(r, B)) { r = sub(r, B); k ++; } C.push_back(k); if (j < A.size()) r.insert(r.begin(), A[A.size() - j - 1]); if (r.size() > 1 && r.back() == 0) r.pop_back(); j++; } reverse(C.begin(), C.end()); while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; }
【算法基础】基础算法（二）--（高精度、前缀和、差分）（下）https://developer.aliyun.com/article/1514664?spm=a2c6h.13148508.setting.28.4b904f0ejdbHoA
