高精度计算CSP-J

💡 核心思想

当运算结果超出标准数据类型范围时（如 `long long` 最多约 19 位），需要模拟人工竖式计算的过程，用数组存储每一位数字，逐位进行加减乘除运算。核心思想是"用字符串/数组表示大数，按位运算处理进位和借位"。

🎯 直觉理解

想象你小学时做的竖式加减法：个位对齐，从右往左逐位相加，满 10 进 1。高精度就是把这个过程写成程序：用数组的每个元素存一位数字，模拟进位和借位。

📝 算法流程

1. 用字符串读入大数，反转后存入数组（个位在下标 0）
2. 加法：逐位相加，处理进位（和 >= 10 则进 1）
3. 减法：逐位相减，处理借位（差 < 0 则向高位借 1）
4. 乘法：用乘数的每一位去乘被乘数的所有位，累加并处理进位
5. 除法：逐位试商，从高位到低位处理余数
6. 最后去除前导零，反转输出

$$\text{加法：}c_i = (a_i + b_i + carry) \bmod 10,quad carry = \lfloor (a_i + b_i + carry) / 10 \rfloor$$

$$\text{乘法：}c_{i+j} += a_i \times b_j,\text{ 然后统一处理进位}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

// 高精度加法：返回 a + b（a, b 为非负整数，以字符串表示）
string add(string a, string b) {
    string res;
    int i = a.size() - 1, j = b.size() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        res.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

// 高精度减法：返回 a - b（保证 a >= b）
string sub(string a, string b) {
    string res;
    int i = a.size() - 1, j = b.size() - 1, borrow = 0;
    while (i >= 0) {
        int diff = (a[i] - '0') - borrow - (j >= 0 ? b[j] - '0' : 0);
        if (diff < 0) { diff += 10; borrow = 1; }
        else borrow = 0;
        res.push_back(diff + '0');
        i--; j--;
    }
    while (res.size() > 1 && res.back() == '0') res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}

// 高精度乘法：返回 a * b
string mul(string a, string b) {
    if (a == "0" || b == "0") return "0";
    vector res(a.size() + b.size(), 0);
    for (int i = a.size() - 1; i >= 0; i--)
        for (int j = b.size() - 1; j >= 0; j--)
            res[i + j + 1] += (a[i] - '0') * (b[j] - '0');
    for (int i = res.size() - 1; i > 0; i--) {
        res[i - 1] += res[i] / 10;
        res[i] %= 10;
    }
    string ans;
    int i = 0; while (i < res.size() && res[i] == 0) i++;
    for (; i < res.size(); i++) ans.push_back(res[i] + '0');
    return ans;
}

int main() {
    string a = "123456789123456789";
    string b = "987654321987654321";
    cout << add(a, b) << endl;
    cout << sub(b, a) << endl;
    cout << mul(a, b) << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目