高精度运算

概念讲解

什么是高精度？

当数据超出基本类型的范围时，需要用数组模拟大数运算。

存储方式

用数组存储每一位，低位在前或高位在前。

12// 低位在前：123 存储为 [3, 2, 1]
// 高位在前：123 存储为 [1, 2, 3]

高精度加法

1234567891011vector<int> add(vector<int>& a, vector<int>& b) {
    vector<int> c;
    int carry = 0;
    for (int i = 0; i < a.size() || i < b.size() || carry; i++) {
        if (i < a.size()) carry += a[i];
        if (i < b.size()) carry += b[i];
        c.push_back(carry % 10);
        carry /= 10;
    }
    return c;
}

高精度减法

1234567891011121314151617vector<int> sub(vector<int>& a, vector<int>& b) {
    vector<int> c;
    int borrow = 0;
    for (int i = 0; i < a.size(); i++) {
        int diff = a[i] - borrow;
        if (i < b.size()) diff -= b[i];
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        c.push_back(diff);
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

高精度乘法

12345678910vector<int> mul(vector<int>& a, int b) {
    vector<int> c;
    int carry = 0;
    for (int i = 0; i < a.size() || carry; i++) {
        if (i < a.size()) carry += a[i] * b;
        c.push_back(carry % 10);
        carry /= 10;
    }
    return c;
}

高精度除法

高精度除法分为两类：大数除以小数（除数为 int）和大数除以大数。初赛主要考查前者。

大数除以小数

除法与加减乘不同，需要从高位开始计算，模拟手工除法的过程：

1. 从最高位开始，将当前位的值累加到余数 remainder 中
2. 用 remainder 除以除数，得到当前位的商
3. 更新余数为 remainder % b
4. 继续处理下一位

由于数组是低位在前存储的，所以需要从数组末尾（高位）向开头遍历：

123456789101112vector<int> divide(vector<int>& a, int b) {
    vector<int> c;
    int remainder = 0;
    for (int i = a.size() - 1; i >= 0; i--) {
        remainder = remainder * 10 + a[i];
        c.push_back(remainder / b);
        remainder %= b;
    }
    reverse(c.begin(), c.end());
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

说明：

• remainder * 10 + a[i]：将上一步的余数乘以 10，加上当前位，得到当前待除的数
• remainder / b：当前位的商
• remainder %= b：更新余数
• 由于从高位开始算，商是高位在前存入 c 的，最后需要 reverse 转回低位在前
• 去除前导零（结果数组末尾的零，即高位的零）

带余数的除法

如果需要同时得到余数，可以通过引用参数返回：

123456789101112vector<int> divide(vector<int>& a, int b, int& remainder) {
    vector<int> c;
    remainder = 0;
    for (int i = a.size() - 1; i >= 0; i--) {
        remainder = remainder * 10 + a[i];
        c.push_back(remainder / b);
        remainder %= b;
    }
    reverse(c.begin(), c.end());
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

考点分析

初赛考查方式

1. 程序阅读： 高精度运算程序
2. 编程题： 大数运算

常见考点

• 高精度加法
• 高精度减法（含 a < b 的处理）
• 高精度乘法（大数乘小数、大数乘大数）
• 高精度除法（大数除以小数，从高位开始计算）
• 进位与借位处理
• 前导零去除

例题精讲

例题 1：高精度加法

题目： 计算 999 + 1。

解答：

  999
+   1
-----
 1000

答案是 1000。

练习题

1. 实现高精度加法。

1234567891011vector<int> add(vector<int>& a, vector<int>& b) {
    vector<int> c;
    int carry = 0;
    for (int i = 0; i < a.size() || i < b.size() || carry; i++) {
        if (i < a.size()) carry += a[i];
        if (i < b.size()) carry += b[i];
        c.push_back(carry % 10);
        carry /= 10;
    }
    return c;
}

2. 实现高精度乘法（大数乘小数）。

12345678910vector<int> mul(vector<int>& a, int b) {
    vector<int> c;
    int carry = 0;
    for (int i = 0; i < a.size() || carry; i++) {
        if (i < a.size()) carry += a[i] * b;
        c.push_back(carry % 10);
        carry /= 10;
    }
    return c;
}

3. 计算 100 的阶乘。

12345678910111213vector<int> factorial(int n) {
    vector<int> result = {1};
    for (int i = 2; i <= n; i++) {
        result = mul(result, i);
    }
    return result;
}

// 输出
vector<int> ans = factorial(100);
for (int i = ans.size() - 1; i >= 0; i--) {
    cout << ans[i];
}

4. 实现高精度除法（大数除以小数，返回商和余数）。

123456789101112vector<int> divide(vector<int>& a, int b, int& remainder) {
    vector<int> c;
    remainder = 0;
    for (int i = a.size() - 1; i >= 0; i--) {
        remainder = remainder * 10 + a[i];
        c.push_back(remainder / b);
        remainder %= b;
    }
    reverse(c.begin(), c.end());
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

易错点

⚠️ 注意：

1. 注意进位和借位处理
2. 结果要去除前导零
3. 低位在前便于进位
4. 注意数组大小
5. 除法必须从高位开始计算（与加减乘方向相反）
6. 除法的商需要 reverse 转回低位在前存储