高精度

高精度加法

#include <bits/stdc++.h>
using namespace std;
const int N = 550;
vector<int> add(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int lena = a.length(), lenb = b.length();
    int len = max(lena, lenb);
    vector<int> res(len + 1);
    for (int i = 0; i < len; i++) {
        res[i] += i < lena ? a[i] - '0' : 0;
        res[i] += i < lenb ? b[i] - '0' : 0;
        res[i + 1] += res[i] / 10;
        res[i] %= 10;
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}
int main() {
    string a, b;
    cin >> a >> b;
    vector<int> res = add(a, b);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
    }
    cout << endl;
    return 0;
}

高精度减法

#include <bits/stdc++.h>
using namespace std;

vector<int> sub(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int lena = a.length(), lenb = b.length();
    int len = max(lena, lenb);
    vector<int> res(len + 1);
    for (int i = 0; i < len; i++) {
        res[i] += i < lena ? a[i] - '0' : 0;
        res[i] -= i < lenb ? b[i] - '0' : 0;
        if (res[i] < 0) {
            res[i + 1]--;
            res[i] += 10;
        }
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}
int main() {
    string a, b;
    cin >> a >> b;
    vector<int> res = sub(a, b);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
    }
    cout << endl;
    return 0;
}

高精度乘法

#include <bits/stdc++.h>
using namespace std;

vector<int> mul(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int lena = a.length(), lenb = b.length();
    vector<int> res(lena + lenb + 1);
    for (int i = 0; i < lena; i++) {
        for (int j = 0; j < lenb; j++) {
            res[i + j] += (a[i] - '0') * (b[j] - '0');
        }
    }
    for (int i = 0; i + 1 < res.size(); i++) {
        res[i + 1] += res[i] / 10;
        res[i] %= 10;
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    string a, b;
    cin >> a >> b;
    vector<int> res = mul(a, b);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
    }
    cout << endl;
    return 0;
}

高精度乘低精度

#include <bits/stdc++.h>
using namespace std;

vector<int> mul(string a, int b) {
    reverse(a.begin(), a.end());
    int lena = a.length();
    vector<int> res(lena);
    for (int i = 0; i < lena; i++) {
        res[i] = b * (a[i] - '0');
    }
    for (int i = 0; i + 1 < res.size(); i++) {
        res[i + 1] += res[i] / 10;
        res[i] %= 10;
    }
    while (res.back() > 10) {
        int x = res.back();
        res.back() = x % 10;
        res.push_back(x / 10);
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    string a;
    int b;
    cin >> a >> b;
    vector<int> res = mul(a, b);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
    }
    cout << endl;
    return 0;
}

高精度除以低精度

#include <bits/stdc++.h>
using namespace std;

vector<int> div(string a, int b) {
    int lena = a.length();
    vector<int> res;
    long long x = 0;
    for (int i = 0; i < lena; i++) {
        x = x * 10 + (a[i] - '0');
        if (!res.empty() || x / b > 0) {
            res.push_back(x / b);
        }
        x %= b;
    }
    if (res.empty()) res.push_back(0);
    return res;
}

int main() {
    string a;
    int b;
    cin >> a >> b;
    vector<int> res = div(a, b);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
    }
    cout << endl;
    return 0;
}

高精度除法

#include <bits/stdc++.h>
using namespace std;
struct BigInt {
    vector<int> d;

    BigInt() {}

    BigInt(const string& s) {
        for (int i = s.size() - 1; i >= 0; i--) {
            d.push_back(s[i] - '0');
        }
    }

    void trim() {
        while (d.size() > 1 && d.back() == 0) d.pop_back();
    }

    friend BigInt operator+(const BigInt& lhs, const BigInt& rhs) {
        BigInt res;
        const vector<int>& a = lhs.d;
        const vector<int>& b = rhs.d;
        vector<int>& c = res.d;
        int lena = a.size(), lenb = b.size();
        int len = max(lena, lenb);
        c.resize(len + 1, 0);

        for (int i = 0; i < len; i++) {
            if (i < lena) c[i] += a[i];
            if (i < lenb) c[i] += b[i];
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
        while (c.size() > 1 && c.back() == 0) c.pop_back();
        return res;
    }

    friend BigInt operator-(const BigInt& lhs, const BigInt& rhs) {
        BigInt res;
        const vector<int>& a = lhs.d;
        const vector<int>& b = rhs.d;
        vector<int>& c = res.d;
        int lena = a.size(), lenb = b.size();
        int len = max(lena, lenb);
        c.resize(len, 0);
        for (int i = 0; i < len; i++) {
            if (i < lena) c[i] += a[i];
            if (i < lenb) c[i] -= b[i];
            if (c[i] < 0) {
                c[i] += 10;
                c[i + 1]--;
            }
        }
        while (c.size() > 1 && c.back() == 0) c.pop_back();
        return res;
    }

    friend BigInt operator*(const BigInt& lhs, int b) {
        BigInt res;
        const vector<int>& a = lhs.d;
        vector<int>& c = res.d;
        int lena = a.size();
        int len = lena;
        c.resize(len + 1, 0);

        for (int i = 0; i < len; i++) {
            c[i] += a[i] * b;
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
        while (c[len] >= 10) {
            c.push_back(c[len] / 10);
            c[len++] %= 10;
        }
        while (c.size() > 1 && c.back() == 0) c.pop_back();
        return res;
    }

    bool operator<(const BigInt& b) const {
        if (d.size() != b.d.size()) return d.size() < b.d.size();
        for (int i = d.size() - 1; i >= 0; i--)
            if (d[i] != b.d[i]) return d[i] < b.d[i];
        return false;
    }

    friend istream& operator>>(istream& is, BigInt& x) {
        string s;
        is >> s;
        x = BigInt(s);
        return is;
    }
    friend ostream& operator<<(ostream& os, const BigInt& x) {
        for (int i = x.d.size() - 1; i >= 0; i--) {
            os << x.d[i];
        }
        return os;
    }
};

pair<BigInt, BigInt> divmod(BigInt A, BigInt B) {
    BigInt Q, R("0");
    Q.d.assign(A.d.size(), 0);
    for (int i = A.d.size() - 1; i >= 0; i--) {
        R.d.insert(R.d.begin(), A.d[i]);
        R.trim();
        int q = 0;
        while (!(R < B)) {
            R = R - B;
            q++;
        }
        Q.d[i] = q;
    }
    Q.trim();
    return {Q, R};
}

int main() {
    BigInt a, b;
    cin >> a >> b;
    auto [c, d] = divmod(a, b);
    cout << c << endl;
    cout << d << endl;
    return 0;
}

压位高精度乘法

高精度乘法加强版

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LEN = 5000;
const int w = 9;
const int base = 1000000000;
vector<int> mul(const vector<int>& a, const vector<int>& b) {
    vector<int> c(a.size() + b.size() + 1);
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
            // 避免爆long long
            ll now = c[i + j] + 1LL * a[i] * b[j];
            c[i + j] = now % base;
            c[i + j + 1] += now / base;
        }
    }
    for (int i = 0; i + 1 < c.size(); i++) {
        c[i + 1] += c[i] / base;
        c[i] %= base;
    }
    // 去掉前导0
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}
int calc(const vector<int>& a, int k) {
    int x = a[k / w];
    for (int i = 0; i < k % w; i++) {
        x = x / 10;
    }
    return x % 10;
}
int main() {
    string a, b;
    cin >> a >> b;
    // 翻转
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    // 压位
    vector<int> va, vb;
    for (int i = 0; i < a.size(); i += w) {
        int x = 0;
        for (int j = i + w - 1; j >= i; j--) {
            x = x * 10 + (j < a.size() ? a[j] - '0' : 0);
        }
        va.push_back(x);
    }
    for (int i = 0; i < b.size(); i += w) {
        int x = 0;
        for (int j = i + w - 1; j >= i; j--) {
            x = x * 10 + (j < b.size() ? b[j] - '0' : 0);
        }
        vb.push_back(x);
    }
    vector<int> c = mul(va, vb);
    // 输出补0
    printf("%d", c.back());
    for (int i = (int)c.size() - 2; i >= 0; i--) {
        printf("%09d", c[i]);
    }
    return 0;
}

重载运算符写法

#include <bits/stdc++.h>
using namespace std;
struct BigInt {
    vector<int> d;

    // 默认构造函数
    BigInt() {}

    // 用 string 构造
    BigInt(const string& s) {
        for (int i = s.size() - 1; i >= 0; i--) {
            d.push_back(s[i] - '0');
        }
    }

    // 用 int 构造，需要是非负整数
    BigInt(int x) {
        if (x == 0) {
            d.push_back(0);
            return;
        }
        while (x > 0) {
            d.push_back(x % 10);
            x /= 10;
        }
    }

    // 重载加法运算符
    friend BigInt operator+(const BigInt& lhs, const BigInt& rhs) {
        BigInt res;
        const vector<int>& a = lhs.d;
        const vector<int>& b = rhs.d;
        vector<int>& c = res.d;
        int lena = a.size(), lenb = b.size();
        int len = max(lena, lenb);
        c.resize(len + 1, 0);

        for (int i = 0; i < len; i++) {
            if (i < lena) c[i] += a[i];
            if (i < lenb) c[i] += b[i];
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
        while (c.size() > 1 && c.back() == 0) c.pop_back();
        return res;
    }

    // 重载减法运算符
    friend BigInt operator-(const BigInt& lhs, const BigInt& rhs) {
        BigInt res;
        const vector<int>& a = lhs.d;
        const vector<int>& b = rhs.d;
        vector<int>& c = res.d;
        int lena = a.size(), lenb = b.size();
        int len = max(lena, lenb);
        c.resize(len, 0);
        for (int i = 0; i < len; i++) {
            if (i < lena) c[i] += a[i];
            if (i < lenb) c[i] -= b[i];
            if (c[i] < 0) {
                c[i] += 10;
                c[i + 1]--;
            }
        }
        while (c.size() > 1 && c.back() == 0) c.pop_back();
        return res;
    }

    friend BigInt operator*(const BigInt& lhs, int b) {
        BigInt res;
        const vector<int>& a = lhs.d;
        vector<int>& c = res.d;
        int lena = a.size();
        int len = lena;
        c.resize(len + 1, 0);

        for (int i = 0; i < len; i++) {
            c[i] += a[i] * b;
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
        while (c[len] >= 10) {
            c.push_back(c[len] / 10);
            c[len++] %= 10;
        }
        while (c.size() > 1 && c.back() == 0) c.pop_back();
        return res;
    }

    friend BigInt operator*(const BigInt& lhs, const BigInt& rhs) {
        BigInt res;
        const vector<int>& a = lhs.d;
        const vector<int>& b = rhs.d;
        vector<int>& c = res.d;
        int lena = a.size();
        int lenb = b.size();
        int len = lena + lenb + 1;
        c.resize(len, 0);

        for (int i = 0; i < lena; i++) {
            for (int j = 0; j < lenb; j++) {
                c[i + j] += a[i] * b[j];
            }
        }
        for (int i = 0; i + 1 < len; i++) {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
        while (c.size() > 1 && c.back() == 0) c.pop_back();
        return res;
    }

    friend BigInt operator/(const BigInt& lhs, int b) {
        BigInt res;
        const vector<int>& a = lhs.d;
        vector<int>& c = res.d;
        int lena = a.size();
        long long rem = 0;
        for (int i = lena - 1; i >= 0; i--) {
            rem = rem * 10 + a[i];
            if (!c.empty() || rem / b > 0) {
                c.push_back(rem / b);
            }
            rem %= b;
        }
        if (c.empty()) c.push_back(0);
        reverse(c.begin(), c.end());
        return res;
    }

    // 重载输出流运算符
    friend ostream& operator<<(ostream& os, const BigInt& x) {
        for (int i = x.d.size() - 1; i >= 0; i--) {
            os << x.d[i];
        }
        return os;
    }
};

int main() {
    string a;
    int b;
    cin >> a >> b;
    BigInt A = a;
    BigInt C = A / b;
    cout << C << endl;
    return 0;
}

题目

• 麦森数（重制版 mini） 用 $\log 10$ 计算位数

• 麦森数（重制版） 快速幂+固定长度的高精度乘法

• 麦森数（重制版 Pro） 快速幂+压位高精度

• 组合数计算 0

• 【SDOI2009】SuperGCD