大整数四则运算

1. 高精度加法
   

   #include <iostream>
   #include <vector>
   #include <string>
   
   using namespace std;
   const int N = 1e6 + 6;
   string a, b;
   vector<int> A, B;
   
   vector<int> add(vector<int> &A, vector<int> &B) {
       vector<int> C;
       int t = 0;
       int lenA = A.size(), lenB = B.size(), lim = max(lenA, lenB);
       for (int i = 0; i < lim; ++i) {
           if (i < lenA) t += A[i];
           if (i < lenB) t += B[i];
           C.push_back(t % 10);
           t /= 10;
       }
       if (t) C.push_back(1);
       return C;
   }
   
   int main() {
       cin >> a >> b;
       int lenA = a.size(), lenB = b.size();
       for (int i = lenA - 1; i >= 0; --i) {
           A.push_back(a[i] - '0');
       }
       for (int i = lenB - 1; i >= 0; --i) {
           B.push_back(b[i] - '0');
       }
       auto C = add(A, B);
       int lenC = C.size();
       for (int i = lenC - 1; i >= 0; --i) {
           cout << C[i];
       }
       return 0;
   }

   逆序vector存储大整数比较方便，
   操作是定义一个临时变量t，
   遍历两数对应位加到t上，
   模十push_back到vector尾部,
   除以十作为进位信息。

2. 大整数相减
   

   #include <bits/stdc++.h>
   
   using namespace std;
   
   vector<int> 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 A[i] > B[i];
       }
       return true;
   }
   
   auto sub(vector<int> A, vector<int> B) { // 默认A >= 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);
           if (t < 0) t = 1;
           else t = 0;
       }
       while (C.size() > 1 && C.back() == 0) C.pop_back();
       return C;
   }
   
   
   int main() {
       string a, b;
       cin >> a >> b;
       int lenA = a.length(), lenB = b.length();
       for (int i = lenA - 1; i >= 0; --i) {
           A.push_back(a[i] - '0');
       }
       for (int i = lenB - 1; i >= 0; --i) {
           B.push_back(b[i] - '0');
       }
       bool f = 0;
       if (!cmp(A, B)) swap(A, B), f = 1; // 特判如果结果是负数，只需计算-(B-A)即可。
       auto C = sub(A, B);
       int lenC = C.size();
       if (f) putchar('-');
       for (int i = lenC - 1; i >= 0; --i) {
           printf("%d", C[i]);
       }
       return 0;
   }

   核心代码是借位的计算，对应位置A减去B（若存在）再减去上一位的进位，将结果加十模十push_back进C（加十模十是为了抹掉负数结果），如果结果为负数，表明借位为1，否则没有借位。

   需要注意的细节：该模板默认A>=B，若结果为负，需要在外部做相应判断。

3. 大整数乘小整数
   

   #include <bits/stdc++.h>
   
   using namespace std;
   
   auto multiply(vector<int> &A, int B) {
       vector<int> C;
       int lenA = A.size();
       int t = 0;
       for (int i = 0; i < lenA || t; ++i) {
           if (i < lenA) t += A[i] * B;
           C.push_back(t % 10);
           t /= 10;
       }
       while (C.size() > 1 && C.back() == 0) C.pop_back();
       return C;
   }
   
   int main() {
       string a;
       int b;
       cin >> a >> b;
       vector<int> A;
       for (int i = a.size() - 1; i >= 0; --i) {
           A.push_back(a[i] - '0');
       }
       auto C = multiply(A, b);
       for (int i = C.size() - 1; i >= 0; --i) {
           printf("%d", C[i]);
       }
       return 0;
   }

   思想与大整数相加类似，注意去除前导零即可。

4. 大整数除以小整数
   

   #include <bits/stdc++.h>
   
   using namespace std;
   
   auto divide(vector<int> &A, int B, int &r) {
       vector<int> C;
       int lenA = A.size();
       r = 0;
       for (int i = lenA - 1; i >= 0; --i) {
           r = r * 10 + A[i];
           C.push_back(r / B);
           r %= B;
       }
       reverse(C.begin(), C.end());
       while (C.size() > 1 && C.back() == 0) C.pop_back();
       return C;
   }
   
   int main() {
       string a;
       int b;
       cin >> a >> b;
       vector<int> A;
       for (int i = a.size() - 1; i >= 0; --i) {
           A.push_back(a[i] - '0');
       }
       int r;
       auto c = divide(A, b, r);
       for (int i = c.size() - 1; i >= 0; --i) {
           printf("%d", c[i]);
       }
       cout << "\n" << r;
       return 0;
   }

   为了与前面三则运算统一，同样逆序存储，实际遍历从高位开始，每次循环时从高位借位*10加上当前位数字，结果除以push_back进C，模B用于下一次借位。