「高精度 乘/除 低精度」y 总在基础课已经讲过了，最近遇到实际的题目需要使用高精度乘以高精度，因此总结一下「高精度 乘/除 高精度」的模板。

高精度乘高精度

基本思想先将 A[i]*B[j] 放在 C[i+j] 上，然后过一遍 C 处理进位即可

// O(nm)
// C = A * B, A >= 0, B >= 0
vector<int> mul(const vector<int> &A, const vector<int> &B) {
    vector<int> C(A.size() + B.size());
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < B.size(); j++) {
            C[i + j] += A[i] * B[j];
        }
    }
    int t = 0;
    for (int i = 0; i < C.size(); i++) {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

高精度除以高精度

减法模拟除法: https://www.bilibili.com/video/BV1iK4y1L7om/?spm_id_from=333.788.videocard.8

例子:
78945/345
78945-34500*2 = 9945 (不断减 34500 直到不够减为止)
9945-3450*2 = 3045
3045-345*8= 285
因此，商就是 228, 余数就是 285

总时间复杂度: O(n-m * (n))，只能通过 8/12 个测试数据，因此能用「高精度/低精度」尽量不用「高精度/高精度」

// O((n-m)*n)
pair<vector<int>, vector<int>> div(vector<int> A, const vector<int> &B) {
    vector<int> C, R;
    int n = A.size(), m = B.size(), d = n - m;
    C.resize(d + 1, 0);
    // 枚举补 0 的个数
    for (int len = d; len >= 0; len--) {
        vector<int> Bp(len, 0);
        for (int x : B) Bp.push_back(x);

        // A >= Bp
        while (!cmp(A, Bp)) {
            C[len] += 1;
            A = sub(A, Bp);
        }
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    R = A;
    return make_pair(C, R);
}

代码

• https://github.com/upupming/algorithm/blob/master/acwing/%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E8%AF%BE/%E7%AC%AC%E4%B8%80%E8%AE%B2%20%E5%9F%BA%E7%A1%80%E7%AE%97%E6%B3%95/%E9%AB%98%E7%B2%BE%E5%BA%A6/
• https://github.com/upupming/algorithm/blob/master/template.md