高精度

高精度加法：A, B 的位数大约 10^6
高精度减法：A, B 的位数大约 10^6
高精度乘法：A 的位数大约 10^6，a <= 10^9
高精度除法

大整数在 C++ 中采用数组来存储。

存储时采用 低位存储 的方式，这样有利于进位，例如 A = 4869，存储到数组中应该是 [9, 6, 8, 4]，此时进位时在数组的末尾添加一个数字，较为简单。

高精度加法

每次在计算每一位的时候，都有三个数参与运算：

Ai：加数
Bi：被加数
t：进位信号，上一位是否产生了进位

最后记得判断最后一位高位是否产生了进位，需不需要补 1。

cpp

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(1);
    }

    return C;
}

高精度减法

在计算减法的时候，分为两种情况：

Ai - Bi >= 0：结果就是 Ai - Bi
Ai - Bi < 0：结果是 Ai - Bi + 10，此时还需要向前借位 t
因此以上都需要 - t，其中 t 表示后一位是否向它借了位

保证 A >= B，最高位不会出现借位。因此需要自行实现判断函数。

cpp

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;
        }
    }
    
    // 消除前导 0
    while (C.size() > 1 && C.back() == 0) {
        C.pop_back();
    }
    return C;
}

注意两种结果用 (t + 10) % 10 合二为一。以及注意消除前导 0，消除前导 0 的时候需要注意 C 数组的大小，如果是 1，说明 C = 0，不需要消除，其他情况都需要消除高位的 0。

高精度乘法

类似高精度加法：

cpp

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;
    }
    // 消除前导 0
    while (C.size() > 1 && C.back() == 0) {
        C.pop_back();
    }
    return C;
}

循环的意思是：

i < A.size()：要么 i 没有循环完
t：要么 t 不为零

这样写不太好，最好分开来写更清楚。

cpp

vector<int> mul(vector<int> &A, int b) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++) {
        t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (t) {
        C.push_back(t % 10);
        t /= 10;
    }
    // 消除前导 0
    while (C.size() > 1 && C.back() == 0) {
        C.pop_back();
    }
    return C;
}

高精度除法

TODO：没看完 58:00

压位

以加法压位为例：

cpp

// ...
    for (int i = a.size() - 1, s = 0, j = 0, t = 1; i >= 0; i --) {
        s += (a[i] - '0') * t;
        t *= 10;
        j ++;

        if (j == 9 || i == 0) {
            A.push_back(s);
            s = 0;
            j = 0;
            t = 1;
        }
    }

把 9 个数压到一个 int 中，例如原来是 vec = [1, 2, 3, 4] 表示 4321，现在是 vec = [4321] 表示 4321。

加法函数：其中 base = 1e9，压 9 位是因为 int 最大就是 2147483647，是 2e10。

cpp

// ...
    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 % base);
        t /= base;
    }

    if (t) {
        C.push_back(t);
    }

输出格式的一些小问题：

cpp

// ...
    cout << C.back();
    for (int i = C.size() - 2; i >= 0; i --) {
        printf("%09d", C[i]);
    }

这是为了防止下面这个案例：

cpp

16240938935313469329483607235163202602496481254606
97843363503439085364101037637514427308246606234751

11408430243875255469358464487267762991074387489357

114084302438752554693584644872677629910743087489357

注意到 087489357 变成了 87489357，如果直接 cout 就会是这个错误结果。应该是 printf("%09d", C[i]); 但是首 9 位又不能有前导零。

AC791. 高精度加法

高精度 ​

高精度加法 ​

高精度减法 ​

高精度乘法 ​

高精度除法 ​

压位 ​

高精度

高精度加法

高精度减法

高精度乘法

高精度除法

压位