高精度整数：从表示到基本运算

当题目中的整数超过 C++ 内置整数类型的范围时，可以把数字拆成一位一位的十进制数，再用数组模拟竖式运算。这类方法通常称为高精度。

1. 什么时候需要高精度

常见的 int 通常只能表示约 21 亿范围内的整数；long long 通常能表示到约 9.22 × 10^18。具体范围由类型标准和实现决定，写题时可使用 <limits> 查看上限。

例如 100! 约有 158 位，无法放进 long long。高精度能按题目需要保存更多位，但运算会比内置整数慢，也要自己处理进位、借位和前导零。

2. 统一数字表示

本文用 vector<int> 保存非负整数，低位放在下标 0。例如十进制数 5072 表示为 {2, 7, 0, 5}。计算完成后去掉多余的高位零，但至少保留一位，因此 0 表示为 {0}。

本文的函数处理非负整数；减法要求被减数不小于减数。负数需要额外保存符号，本文先不扩展到带符号大整数。

#include <bits/stdc++.h>
using namespace std;
using Big = vector<int>; // 低位在前，每个元素是一位十进制数

Big parseBig(const string& s) {
    Big a;
    for (int i = static_cast<int>(s.size()) - 1; i >= 0; --i) {
        if (!isdigit(static_cast<unsigned char>(s[i])))
            throw invalid_argument("输入必须是非负十进制整数");
        a.push_back(s[i] - '0');
    }
    if (a.empty()) a.push_back(0);
    while (a.size() > 1 && a.back() == 0) a.pop_back();
    return a;
}

string toString(const Big& a) {
    string s;
    for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i)
        s.push_back(char('0' + a[i]));
    return s;
}

int compareBig(const Big& a, const Big& b) {
    if (a.size() != b.size()) return a.size() < b.size() ? -1 : 1;
    for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {
        if (a[i] != b[i]) return a[i] < b[i] ? -1 : 1;
    }
    return 0;
}

Big addBig(const Big& a, const Big& b) {
    Big c;
    int carry = 0;
    for (int i = 0; i < static_cast<int>(max(a.size(), b.size())) || carry; ++i) {
        int sum = carry;
        if (i < static_cast<int>(a.size())) sum += a[i];
        if (i < static_cast<int>(b.size())) sum += b[i];
        c.push_back(sum % 10);
        carry = sum / 10;
    }
    return c;
}

// 前提：a >= b
Big subtractBig(const Big& a, const Big& b) {
    if (compareBig(a, b) < 0)
        throw invalid_argument("subtractBig 要求 a >= b");
    Big c = a;
    int borrow = 0;
    for (int i = 0; i < static_cast<int>(c.size()); ++i) {
        int digit = c[i] - borrow - (i < static_cast<int>(b.size()) ? b[i] : 0);
        borrow = digit < 0;
        if (borrow) digit += 10;
        c[i] = digit;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

Big multiplyBig(const Big& a, const Big& b) {
    Big c(a.size() + b.size() + 1, 0);
    for (int i = 0; i < static_cast<int>(a.size()); ++i) {
        for (int j = 0; j < static_cast<int>(b.size()); ++j)
            c[i + j] += a[i] * b[j];
    }
    for (int i = 0; i + 1 < static_cast<int>(c.size()); ++i) {
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

// 返回 a 除以正整数 divisor 的商，余数写入 remainder
Big divideBySmall(const Big& a, int divisor, int& remainder) {
    if (divisor <= 0) throw invalid_argument("除数必须为正整数");
    Big q(a.size(), 0);
    long long rem = 0;
    for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {
        long long current = rem * 10 + a[i];
        q[i] = static_cast<int>(current / divisor);
        rem = current % divisor;
    }
    while (q.size() > 1 && q.back() == 0) q.pop_back();
    remainder = static_cast<int>(rem);
    return q;
}

int main() {
    string x, y;
    cin >> x >> y;
    Big a = parseBig(x);
    Big b = parseBig(y);

    cout << "a + b = " << toString(addBig(a, b)) << '\n';
    cout << "a * b = " << toString(multiplyBig(a, b)) << '\n';
    if (compareBig(a, b) >= 0)
        cout << "a - b = " << toString(subtractBig(a, b)) << '\n';

    int remainder = 0;
    Big quotient = divideBySmall(a, 7, remainder);
    cout << "a / 7 = " << toString(quotient)
         << ", remainder = " << remainder << '\n';
}

3. 运算过程

加法

从低位到高位逐位相加，把上一位进位加进来。当前位写 sum % 10，进位写 sum / 10。最后可能还剩一位进位，需要追加到结果。

减法

先保证 a >= b，逐位相减；若当前位不够减，就向高位借 1（也就是当前位加 10）。运算后从最高位去掉多余的 0。

乘法

第 i 位与第 j 位的乘积，先累加到结果的第 i + j 位，再统一处理进位。两个有 n、m 位的数，朴素乘法时间复杂度为 O(nm)。

除以小整数

从高位向低位扫描，维护当前余数 rem。把新的一位接到余数后面，商的当前位为 current / divisor，新的余数为 current % divisor。

4. 用高精度求阶乘

用高精度乘以每个小整数即可：

Big factorial(int n) {
    Big result{1};
    for (int i = 2; i <= n; ++i) {
        Big x;
        int value = i;
        while (value > 0) {
            x.push_back(value % 10);
            value /= 10;
        }
        result = multiplyBig(result, x);
    }
    return result;
}