原则

高精度数字的存储是用vector存储的，下标小的是低位，下标大的是高位。

高精度加法

t表示进位。

  1. vector<int> add(vector<int> A, vector<int> B)
  2. {
  3.     vector<int> C;
  4.     int t = 0;
  5.     for (int i = 0; i < A.size() || i < B.size() || t; i ++) {
  6.         if (i < A.size()) {
  7.             t += A[i];
  8.         }
  9.         if (i < B.size()) {
  10.             t += B[i];
  11.         }
  12.         C.push_back(t % 10);
  13.         t /= 10;
  14.     }
  15.     return C;
  16. }

高精度减法

这里的减法保证a > b。
代码里的borrow表示借位。
最后要去掉前导0。

  1. bool cmp(vector<int>& a, vector<int>& b) {
  2.     if (a.size() != b.size()) return a.size() > b.size();
  3.     for (int i = (int) a.size() - 1; i >= 0; i --) {
  4.         if (a[i] != b[i]) return a[i] > b[i];
  5.     }
  6.     return true;
  7. }
  9. vector<int> _minus(vector<int>& a, vector<int>& b) {
  10.     vector<int> c;
  11.     int borrow = 0;
  12.     for (int i = 0; i < (int)a.size(); i ++) {
  13.         int t = a[i] - borrow;
  14.         if (i < (int)b.size()) {
  15.             t = t - b[i];
  16.         }
  17.         if (t >= 0) {
  18.             c.push_back(t);
  19.             borrow = 0;
  20.         } else {
  21.             c.push_back(t + 10);
  22.             borrow = 1;
  23.         }
  24.     }
  26.     while (c.size() > 1 && c.back() == 0) {
  27.         c.pop_back();
  28.     }
  29.     return c;
  30. }

高精度乘法

A是高精度整数，b是int型小整数。
需要去掉前导0（12345*0）。

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < (int)A.size() || t; i ++) {
        if (i < (int)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;
}

高精度除法

高精度除法的计算顺序和加减乘是反的。因此最终答案要reverse一下。
需要去掉前导0。

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 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;
}