信息学竞赛模板（六）— 高精度运算

1 高精度乘法

1.1 高精度整数乘小整数

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;
    }

    return c;
}

1.2 两个高精度数相乘

• 参看例题 LeetCode-43-字符串相乘

//两个高精度数相乘，可以转化为高精度乘低精度，但尽量让低精度数位数大一些，减少计算量
vector<int> big_mul(vector<int> &a, vector<int> &b) {
    vector<int> res(1, 0);
    int pos = 7, zeros = 10000000, n = b.size();
    for (int i = 0; i < n; i += pos) {
        int k = 0;  //将低精度的b扩大为POS位数，减少计算量
        for (int j = min(i + pos, n) - 1; j >= i; --j) {
            k = k * 10 + b[j];
        }
        if (k > 0) {
            auto tmp = mul(a, k);
            for (int j = 0; j < i / pos; ++j) { //从十位开始要往后补０
                tmp = mul(tmp, zeros);
            }
            res = add(res, tmp);
        }
    }
    return res;
}

//高精度乘低精度
vector<int> mul(vector<int> &a, int b) {
    vector<int> res;
    int t = 0;
    for (int i = 0; i < a.size(); ++i) {
        t += a[i] * b;
        res.push_back(t % 10);
        t /= 10;
    }
    while (t) {
        res.push_back(t % 10);
        t /= 10;
    }
    return res;
}

//两个高精度数相加
vector<int> add(vector<int> &a, vector<int> &b) {
    vector<int> res;

    int i = 0, t = 0;
    while (i < a.size() || i < b.size()) {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        res.push_back(t % 10);
        t /= 10;
        i++;
    }
    while (t) {
        res.push_back(t % 10);
        t /= 10;
    }

    return res;
}

2 高精度除法

2.1 高精度整数除小整数

vector<int> div(vector<int> &a, int b) {
    vector<int> c;
    bool is_first = false;  //是否已经开始有除数，避免输出前导0
    int x, t = 0;
    for (int i = a.size() - 1; i >= 0; --i) {
        t = t * 10 + a[i];
        x = t / b;
        if (x || is_first) {
            is_first = true;
            c.push_back(x);
        }
        t %= b;
    }

    return vector<int>(c.rbegin(), c.rend());
}