竞极 Ace

7 高精度运算

GESP C++ 五级：高精度运算精讲

核心目标：理解高精度运算的必要性与核心思想，掌握数组逆序存储方案，熟练实现高精度加法、减法、乘法和除法，掌握比较大小、去除前导零等辅助操作，能解决阶乘之和等综合应用问题。
高精度就是用数组模拟手工竖式运算——数字逆序存储，个位在下标0；加法逐位相加处理进位，减法逐位相减处理借位，乘法双重循环累加，除法逐位试商。

一、考纲定位

根据 CCF 官方考纲，五级知识内容明确包含：“掌握 C++ 数组模拟高精度加法、减法、乘法和除法的相关知识”。

高精度运算在五级考试中的考查分布：

考点 重要程度 典型考法
数组逆序存储方案 ★★★★★ 选择题、代码填空
高精度加法（进位处理） 代码填空高频
高精度减法（借位处理） 代码填空、程序阅读
高精度乘法（双重循环） 代码填空高频
高精度除法（逐位试商） ★★★★☆ 代码填空
去除前导零 代码填空、程序阅读
比较大小 代码填空
综合应用（阶乘之和等） 编程题

高精度运算在五级真题中频繁出现：2023年12月单选第11题考查高精度加法代码行，2025年3月单选第15题考查高精度乘法进位处理，2024年9月单选第14题考查高精度四则运算复杂度与实现要点，2025年6月真题考查高精度除法函数填空。

二、为什么需要高精度运算

C++ 原生整数类型存在范围限制：

类型 范围 大致位数
int -2,147,483,648 ~ 2,147,483,647 约 10 位
long long -9.2×10¹⁸ ~ 9.2×10¹⁸ 约 19 位

当题目要求计算上百位甚至上千位的大数时，int 和 long long 都无法存储。高精度运算通过数组模拟的方式，突破原生类型的位宽限制，实现任意位数的整数运算。

三、核心存储方案

3.1 逆序存储（小端倒序）

高精度运算的基石是将大整数按位拆分，逆序存入数组——个位放在下标 0，十位放在下标 1，以此类推。

示例：存储数字 31415926

数组下标：  0    1    2    3    4    5    6    7
数组内容：  6    2    9    5    1    4    1    3
对应位：   个位  十位  百位  千位 ...

为什么逆序存储？

  1. 进位/借位方向一致：加减法从低位到高位处理，逆序存储后数组从左到右正好对应从低位到高位，进位和借位自然向右传播。
  2. 输出时逆序打印：从数组末尾向前输出即可得到正确顺序的数字。
  3. 代码简洁：循环从下标 0 开始，直观不易出错。

3.2 字符串转数组

string s;
cin >> s;
int a[1005] = {0};   // 初始化全0
int len = s.size();

// 逆序存储：s 的最后一位（个位）存到 a[0]
for (int i = 0; i < len; i++) {
    a[i] = s[len - 1 - i] - '0';
}

关键细节：字符转数字需要 - '0'，因为 '0' 的 ASCII 码是 48，'5' - '0' 得到整数 5。

四、高精度加法

4.1 核心思想

模拟手工加法：从个位开始逐位相加，结果大于等于 10 时向高位进位。

4.2 代码模板

string add(string s1, string s2) {
    int a[1005] = {0}, b[1005] = {0}, c[1005] = {0};
    int len1 = s1.size(), len2 = s2.size();

    // 逆序存储
    for (int i = 0; i < len1; i++) a[i] = s1[len1 - 1 - i] - '0';
    for (int i = 0; i < len2; i++) b[i] = s2[len2 - 1 - i] - '0';

    int len = max(len1, len2);
    int carry = 0;   // 进位

    for (int i = 0; i < len; i++) {
        int sum = a[i] + b[i] + carry;
        c[i] = sum % 10;      // 本位
        carry = sum / 10;     // 进位
    }

    if (carry) c[len] = carry;   // 最高位可能进位

    // 去除前导零并输出
    int start = len;
    while (start > 0 && c[start] == 0) start--;

    string res = "";
    for (int i = start; i >= 0; i--) {
        res += char('0' + c[i]);
    }
    return res;
}

4.3 执行示例

计算 99999999 + 555：

数组a（逆序）：[9,9,9,9,9,9,9,9]
数组b（逆序）：[5,5,5,0,0,0,0,0]

i=0: 9+5+0=14, c[0]=4, carry=1
i=1: 9+5+1=15, c[1]=5, carry=1
i=2: 9+5+1=15, c[2]=5, carry=1
i=3: 9+0+1=10, c[3]=0, carry=1
...
最终 c 数组逆序输出：100005554

4.4 复杂度

时间复杂度 O(n)，其中 n 为两个数的最大位数。

五、高精度减法

5.1 核心思想

模拟手工减法：从个位开始逐位相减，不够减时向高位借位。

重要前提：必须保证被减数 ≥ 减数。如果被减数小于减数，需要先交换两个数，计算后在结果前加负号。

5.2 比较大小

// 返回 true 表示 a >= b
bool compare(string a, string b) {
    if (a.size() != b.size()) return a.size() > b.size();
    return a >= b;
}

5.3 代码模板

string sub(string s1, string s2) {
    bool negative = false;

    // 保证 s1 >= s2
    if (!compare(s1, s2)) {
        swap(s1, s2);
        negative = true;
    }

    int a[1005] = {0}, b[1005] = {0}, c[1005] = {0};
    int len1 = s1.size(), len2 = s2.size();

    for (int i = 0; i < len1; i++) a[i] = s1[len1 - 1 - i] - '0';
    for (int i = 0; i < len2; i++) b[i] = s2[len2 - 1 - i] - '0';

    for (int i = 0; i < len1; i++) {
        if (a[i] < b[i]) {
            a[i] += 10;       // 向高位借1当10
            a[i + 1]--;       // 高位减1
        }
        c[i] = a[i] - b[i];
    }

    // 去除前导零
    int start = len1 - 1;
    while (start > 0 && c[start] == 0) start--;

    string res = "";
    if (negative) res += '-';
    for (int i = start; i >= 0; i--) {
        res += char('0' + c[i]);
    }
    return res;
}

5.4 借位逻辑详解

真题示例（2026年6月五级） ：

高精度减法中，假设两个高精度数按低位在前存储，且已经保证被减数不小于减数。下面处理借位逻辑代码中横线处应填入（ ）。

if (a[i] < b[i]) {
 a[i + 1]--;
 ________________;
}
t = a[i] - b[i];

A. a[i] += 10; B. a[i] -= 10; C. a[i] = 10; D. a[i] = 0;
答案：A

解析：当 a[i] < b[i] 时，需要向高位借 1，当前位加 10 后再减。a[i + 1]-- 已经完成了向高位借 1 的操作，接下来必须让 a[i] += 10，否则当前位的值不足以减去 b[i]。

六、高精度乘法

6.1 核心思想

模拟手工乘法：将一个大数的每一位与另一个大数的每一位相乘，结果累加到对应的位置上。

6.2 核心公式

对于两个数 A 和 B，A 的第 i 位与 B 的第 j 位相乘，结果应累加到结果的第 i+j 位：

c[i + j] += a[i] * b[j];

原理：10^i × 10^j = 10^(i+j)，所以第 i 位和第 j 位相乘的结果应该放在第 i+j 位上。

6.3 代码模板

string multiply(string s1, string s2) {
    if (s1 == "0" || s2 == "0") return "0";

    int a[2005] = {0}, b[2005] = {0}, c[4005] = {0};
    int len1 = s1.size(), len2 = s2.size();

    for (int i = 0; i < len1; i++) a[i] = s1[len1 - 1 - i] - '0';
    for (int i = 0; i < len2; i++) b[i] = s2[len2 - 1 - i] - '0';

    // 双重循环：逐位相乘并累加
    for (int i = 0; i < len1; i++) {
        for (int j = 0; j < len2; j++) {
            c[i + j] += a[i] * b[j];
        }
    }

    // 统一处理进位
    for (int i = 0; i < len1 + len2; i++) {
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }

    // 去除前导零
    int start = len1 + len2 - 1;
    while (start > 0 && c[start] == 0) start--;

    string res = "";
    for (int i = start; i >= 0; i--) {
        res += char('0' + c[i]);
    }
    return res;
}

6.4 执行示例

计算 246 × 65：

数组a（逆序）：[6,4,2]   // 246
数组b（逆序）：[5,6]      // 65

i=0,j=0: c[0] += 6*5 = 30
i=0,j=1: c[1] += 6*6 = 36
i=1,j=0: c[1] += 4*5 = 20  → c[1] = 56
i=1,j=1: c[2] += 4*6 = 24
i=2,j=0: c[2] += 2*5 = 10  → c[2] = 34
i=2,j=1: c[3] += 2*6 = 12

累加后c：[30, 56, 34, 12]
统一进位：
i=0: c[1] += 3, c[0] = 0        → c=[0, 59, 34, 12]
i=1: c[2] += 5, c[1] = 9        → c=[0, 9, 39, 12]
i=2: c[3] += 3, c[2] = 9        → c=[0, 9, 9, 15]
i=3: c[4] += 1, c[3] = 5        → c=[0, 9, 9, 5, 1]

逆序输出：15990
验证：246 × 65 = 15990 ✓

6.5 复杂度

时间复杂度 O(n×m)，其中 n 和 m 分别是两个数的位数。朴素乘法的循环次数与十进制位数完全等长，两数都是 5000 位时，将运行约 2500 万次乘-加-进位。

七、高精度除法（高精度除以低精度）

7.1 核心思想

模拟手工除法：从高位到低位逐位试商，余数乘以 10 加上下一位继续除。

7.2 代码模板（高精度 ÷ 低精度）

string divide(string s, int b, int &remainder) {
    int a[1005] = {0};
    int len = s.size();

    // 注意：除法从高位开始处理，这里正序存储
    for (int i = 0; i < len; i++) a[i] = s[i] - '0';

    int r = 0;   // 余数
    string res = "";

    for (int i = 0; i < len; i++) {
        int cur = r * 10 + a[i];   // 当前被除数
        res += char('0' + cur / b); // 商
        r = cur % b;                // 更新余数
    }
    remainder = r;

    // 去除前导零
    int start = 0;
    while (start < res.size() - 1 && res[start] == '0') start++;
    return res.substr(start);
}

7.3 执行示例

计算 12345 ÷ 12：

i=0: cur = 0*10+1 = 1, 1/12=0, r=1, res="0"
i=1: cur = 1*10+2 = 12, 12/12=1, r=0, res="01"
i=2: cur = 0*10+3 = 3, 3/12=0, r=3, res="010"
i=3: cur = 3*10+4 = 34, 34/12=2, r=10, res="0102"
i=4: cur = 10*10+5 = 105, 105/12=8, r=9, res="01028"

去除前导零：1028
验证：12345 ÷ 12 = 1028 余 9 ✓

八、GESP 五级真题精讲

真题1：高精度加法进位处理（2023年12月第11题）

下面的代码片段用于将两个高精度整数进行相加，横线处应填入（ ）。

for (int i = 0; i < len; i++) {
 c[i] += a[i] + b[i];
 ______________;
 ______________;
}

答案：c[i + 1] = c[i] / 10; 和 c[i] %= 10;

解析：c[i] / 10 得到进位值，存入高位 c[i + 1]；c[i] % 10 得到本位保留的值。两者顺序不能颠倒，因为 c[i] %= 10 会改变 c[i] 的值。

真题2：高精度乘法进位处理（2025年3月第15题）

小杨编写了一个如下的高精度乘法函数，横线处应填写的代码为（ ）。
答案：c[i + j] += a[i] * b[j];

解析：A 的第 i 位与 B 的第 j 位相乘，结果累加到 c 的第 i+j 位。

真题3：高精度减法借位逻辑（2026年6月五级）

高精度减法中，横线处应填入（ ）。

if (a[i] < b[i]) {
 a[i + 1]--;
 ________________;
}
t = a[i] - b[i];

答案：a[i] += 10;

真题4：高精度除法（2025年6月第15题）

小杨编写了一个如下的高精度除法函数，横线上应填写的代码为（ ）。
答案：c.push_back(t % 10), t = t / 10;

解析：每次保存对应位和的最低位数字，去掉最低位数字后，保持进位，循环执行。

真题5：阶乘之和（NOIP 1998，GESP五级练习）

题目：用高精度计算出 S = 1! + 2! + 3! + … + n!（n ≤ 50）。

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

const int N = 100;
int a[N], b[N], c[N];   // a:阶乘, b:累加和, c:临时

int main() {
    int n;
    cin >> n;

    a[0] = 1;   // 阶乘初始为1
    int len_a = 1, len_b = 1;

    for (int i = 1; i <= n; i++) {
        // 计算 i! : a *= i
        int carry = 0;
        for (int j = 0; j < len_a; j++) {
            int t = a[j] * i + carry;
            a[j] = t % 10;
            carry = t / 10;
        }
        while (carry) {
            a[len_a++] = carry % 10;
            carry /= 10;
        }

        // 累加: b += a
        carry = 0;
        for (int j = 0; j < max(len_a, len_b); j++) {
            int t = b[j] + a[j] + carry;
            b[j] = t % 10;
            carry = t / 10;
        }
        len_b = max(len_a, len_b);
        if (carry) b[len_b++] = carry;
    }

    // 输出
    int start = len_b - 1;
    while (start > 0 && b[start] == 0) start--;
    for (int i = start; i >= 0; i--) {
        cout << b[i];
    }
    cout << endl;
    return 0;
}

九、易错点汇总

  1. 忘记逆序存储：高精度数必须逆序存入数组，个位在下标 0。
  2. 忘记 - '0'：字符转数字必须减去 '0' 的 ASCII 码。
  3. 加法忘记处理最后进位：最高位相加后可能产生进位，需要额外存入 c[len]。
  4. 减法未比较大小：必须保证被减数 ≥ 减数，否则需要交换并加负号。
  5. 减法借位逻辑错误：a[i] += 10 和 a[i + 1]-- 缺一不可。
  6. 乘法忘记初始化：c 数组必须初始化为全 0。
  7. 乘法进位处理时机：先累加所有乘积，再统一处理进位。
  8. 乘法位置公式错误：c[i + j] += a[i] * b[j]，不是 c[i] += a[i] * b[j]。
  9. 除法未去除前导零：商的前面可能有多个 0，需要跳过。
  10. 输出时忘记逆序：高精度结果是逆序存储的，输出时必须从高位到低位打印。
  11. 数组大小不足：乘法结果位数最多为两个数位数之和，数组需要开够。

十、速查表

运算 核心公式 关键注意
存储 a[i] = s[len - 1 - i] - '0' 逆序存储，个位在下标 0
加法 c[i] = (a[i] + b[i] + carry) % 10; carry = (a[i] + b[i] + carry) / 10; 最后处理最高进位
减法 if (a[i] < b[i]) { a[i] += 10; a[i + 1]--; } c[i] = a[i] - b[i]; 先比较大小，借位两步都要写
乘法 c[i + j] += a[i] * b[j]; 先累加再统一进位
乘法进位 c[i + 1] += c[i] / 10; c[i] %= 10; 从低位到高位依次处理
除法 cur = r * 10 + a[i]; res += cur / b; r = cur % b; 正序存储，逐位试商
比较 先比位数，位数相同再按字典序比 位数多的数更大
输出 从最高位开始逆序输出 去除前导零

十一、总结

高精度运算是 GESP 五级从“处理普通数据”迈向“处理超大数据”的关键技能。

  1. 高精度用数组模拟手工竖式运算，突破 int 和 long long 的位数限制。
  2. 核心存储方案是逆序存储，个位在下标 0，进位借位方向统一。
  3. 高精度加法：逐位相加，处理进位，最后不要忘记最高位进位。
  4. 高精度减法：先比较大小，保证大减小，借位时 a[i] += 10 和 a[i+1]-- 缺一不可。
  5. 高精度乘法：双重循环 c[i+j] += a[i] * b[j]，先累加再统一进位。
  6. 高精度除法：从高位开始逐位试商，余数乘 10 加下一位继续除。
  7. 所有运算输出前都要去除前导零。
  8. 输出时从最高位开始逆序打印，因为结果是逆序存储的。
  9. 乘法结果位数最多为两个数位数之和，数组大小要留足。
  10. 多练“进位处理”“借位逻辑”“乘法位置公式”“去除前导零”四类代码填空题。

复习建议：先把逆序存储和加法写熟，再攻克减法的借位和比较大小；然后重点练习乘法的双重循环和进位处理，最后掌握除法的逐位试商。考试中先判断题目考的是哪种运算和哪个步骤（进位/借位/位置公式/前导零），再套用对应模板作答。