大整数运算

大整数存储在数组中，低数位存储在小地址，高数位存储在大地址。

大整数加法

两个数A、B均为大整数（A $\geqslant$ 0、B $\geqslant$ 0），C为A $+$ B的和，t为进位。

(1)计算t = A[i]+B[i]+t，此时t中暂存的是没处理进位前的该位加和；

(2)C[i] = t%10，下一位的新进位t更新为t/10；

(3)最后若还有进位，直接放入C最高位中。

// A >= 0, B >= 0, A.size() >= B.size()
vector<int> add(vector<int> &A, vector<int> &B) {
    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;
}

注解：

(1)调用大整数加法需保证A.size() $\geqslant$ B.size()，否则对调A、B。

vector<int> C;
if (A.size() >= B.size())
    C = add(A, B);
else
    C = add(B, A);

(2)设置A.size() $\geqslant$ B.size()则大整数加减法的写法可以统一起来，如果不考虑写法因素，大整数加法不需要A.size() $\geqslant$ B.size()。

// A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B) {
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i++) {
        if (i < A.size()) 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;
}

大整数减法

两个数A、B均为大整数（A $\geqslant$ 0、B $\geqslant$ 0），C为A $-$ B的差，t为借位。

(1)计算t = A[i]-t-B[i]，此时t中暂存的是没处理借位前的该位减差；

(2)C[i] = (t+10)%10（此式表示：t $<$ 0时，t = t+10，t $\geqslant$ 0时，t不变）；

t $<$ 0时，下一位的新借位t更新为1，t $\geqslant$ 0时，下一位的新借位t更新为0；

(3)最后处理一下前导零。

// A >= 0, B >= 0, A >= B
vector<int> sub(vector<int> &A, 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;
}

注解：

(1)调用大整数减法需保证A $\geqslant$ B，否则对调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;
}

vector<int> c;
if (cmp(a, b))
    c = add(a, b);
else
    c = add(b, a); // 此情况输出时需要添加"-"号

大整数乘法

A为大整数，b为普通整数（A $\geqslant$ 0、b $\geqslant$ 0），C为A $\times$ b的积，t为进位。

(1)计算t = A[i]*b+t，此时t中暂存的是没处理进位前的该位乘积；

(2)C[i] = t%10，下一位的新进位t更新为t/10；

(3)若还有进位，按照(2)中的规则继续放入C高位中（代码中将2、3两步合并起来）；

(4)最后处理一下前导零。

// A >= 0, b >= 0
vector<int> mul(vector<int> &A, 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;
    }

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

    return C;
}

大整数除法

A为大整数，b为普通整数（A $\geqslant 0$、b $>$ 0），C为A $\div$ B的商，r为余数。

(1)计算r = r*10+A[i]，此时r中暂存的是当前位的被除数；

(2)C[i] = r/b，下一位的新余数更新为r%b；

(3)将C翻转（因为此时C的低数位存储在小地址，C的高数位存储在大地址，翻转后才符合大整数的存储法则）；

(4)最后处理一下前导零。

// A / b = C ... r, A >= 0, b > 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;
}

---