高精度

高精度加法

const int BASE = 10;

vector<int> add(const vector<int>& A, const 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);

    // clear lead zero
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

高精度减法

vector<int> sub(const vector<int>& A, const vector<int>& 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;
}

高精度乘低精度

主循环用一个变量 $t$ 表示结果，注意以下情况

while(t) C.push_back(t%10), t /= 10;

vector<int> mul(const vector<int>& A, const int b) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || t; i++) {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10), t /= 10;
    }
    return C;
}

高精度除以低精度

vector<int> div(const vector<int>& A, int b) {
    vector<int> C;
    int 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;
}

高精度乘高精度

vector<int> mul(const vector<int>& A, const vector<int>& B) {
    vector<int> C(A.size()+B.size()+10, 0);
    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; i < C.size(); i++) {
        if (C[i] >= 10) C[i+1] += C[i] / 10, C[i] %= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

高精度和高精度的比较

check A < B, return true

bool cmp(const vector<int>& A, const vector<int>& B) {
    // check A <= B
    if (A.size() < B.size()) return true;
    if (A.size() > B.size()) return false;

    if (vector<int>(A.rbegin(), A.rend()) <= vector<int>(B.rbegin(), B.rend())) return true;
    return false;
}

高精度除以高精度

高精度除法重点理解

vector<int> div(vector<int> A, vector<int> B) {
    int dv = A.size() - B.size();
    vector<int> C(dv+1, 0);

    // append suffix zero
    reverse(B.begin(), B.end());
    for (int i = 0; i < dv; i++) B.push_back(0);
    reverse(B.begin(), B.end());

    for (int i = 0; i <= dv; i++) {
        while (!cmp(A, B)) {
            A = sub(A, B);
            C[dv-i]++;
        }
        B.erase(B.begin());
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}