18 高精度运算（大整数）

GESP 5 级CSP-J / NOIP 必备

级别标注：GESP 5 级（考级要求）/ CSP-J、NOIP 必须（竞赛进阶：高精度加法/乘法/减法/除法）。

一、为什么需要高精度

long long 最大约 9.2×10^18，当题目数据范围超过它时运算会溢出。高精度用数组/字符串手工模拟手算过程，实现任意大数的四则运算。

应用场景：GESP 5 级"高精度加法"，NOIP 中大数阶乘、大数乘法、数论组合数等。

形象理解高精度像小学生的竖式笔算：int/long long 装不下的超级大数，就用数组一位一位存，手工模拟进位借位。long long 最多约 9.2×10^18，超过它就必须上高精度。

考级视角GESP 5 级高精度加法是实打实的考点，减法/乘法常以思路题出现。判断标准：题目说“n ≤ 10^1000”或“结果可能超过 64 位整数”，就要立刻想到高精度。

二、存储结构：倒序 + 数组

习惯：个位存下标 0（倒序），好处是进位/借位只需往高位扩展。

C++ 实例

#include <iostream>
#include <string>
using namespace std;
// 字符串转"倒序 int 数组"（低位在前，方便从个位开始运算）
// 返回数字位数
int toArr(const string &s, int a[]) {
    int len = s.size();
    for (int i = 0; i < len; i++) {
        a[i] = s[len - 1 - i] - '0';   // 反转存：a[0] 是个位
    }
    return len;
}
int main() {
    string s = "123456789";
    int a[1000];
    int n = toArr(s, a);
    cout << a[0] << " " << a[1] << " " << a[2] << endl; // 9 8 7（个位在前）
    return 0;
}

输出函数（倒序转回）

C++ 实例

// 倒序数组按正序打印（从最高位 len-1 到最低位 0）
void printArr(int a[], int len) {
    for (int i = len - 1; i >= 0; i--) cout << a[i];
    cout << endl;
}

形象理解倒序存储像把数字倒着写进格子：个位放 0 号格、十位放 1 号格…这样做加法进位时只要往后追加格子，不用整体搬家。

易错点最容易错的是输出方向：存的时候 a[i] = s[len-1-i] - '0'（反转），输出必须 for (i = len-1; i >= 0; i--) 倒着打印。方向记反 = 结果倒着显示，白写。

三、高精度加法

从最低位（下标 0）开始逐位相加，处理进位。

C++ 实例

#include <iostream>
#include <string>
using namespace std;
const int N = 1005;

// 高精度加法：a(la位) + b(lb位) -> c，返回结果位数
int add(int a[], int la, int b[], int lb, int c[]) {
    int len = max(la, lb);
    int carry = 0;                    // 进位
    for (int i = 0; i < len; i++) {
        int sum = (i < la ? a[i] : 0) + (i < lb ? b[i] : 0) + carry;  // 逐位相加+进位
        c[i] = sum % 10;              // 当前位
        carry = sum / 10;             // 新进位
    }
    if (carry) c[len++] = carry;      // 最高位仍有进位则补一位
    return len;
}

int toNum(int a[], const string &s) {   // 字符串转倒序数组
    int len = s.size();
    for (int i = 0; i < len; i++) a[i] = s[len - 1 - i] - '0';
    return len;
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;                  // 直接读字符串避免溢出
    int a[N] = {}, b[N] = {}, c[N] = {};
    int la = toNum(a, s1), lb = toNum(b, s2);
    int lc = add(a, la, b, lb, c);
    for (int i = lc - 1; i >= 0; i--) cout << c[i];   // 倒序输出
    cout << endl;
    return 0;
}

可用万进制/压位（每位存 4 个十进制位）显著提速，进阶再学。

形象理解高精度加法像两列数字从个位对齐逐列相加：sum = a[i] + b[i] + carry，写 sum % 10，进 sum / 10。短的数高位当 0 处理。

易错点两个坑：① 最高位进位要单独处理（if (carry) c[len++] = carry;），漏掉则 999+1 会输出 000；② 数组要 memset 清零，缺位补 0 否则读到垃圾值。

四、高精度减法

从低位减起，不够借位；需先判断大小确定符号。

C++ 实例

// 判断 a >= b（倒序数组及长度）：先比位数，再逐位比
int cmp(int a[], int la, int b[], int lb) {
    if (la != lb) return la > lb ? 1 : -1;   // 位数多的更大
    for (int i = la - 1; i >= 0; i--) {      // 从高位往低位比
        if (a[i] != b[i]) return a[i] > b[i] ? 1 : -1;
    }
    return 0;   // 相等
}

// 大减小：假定 a >= b（减法按位处理借位）
int sub(int a[], int la, int b[], int lb, int c[]) {
    int len = 0;
    int borrow = 0;                   // 借位标志
    for (int i = 0; i < la; i++) {
        int x = a[i] - borrow;        // 当前位先减借位
        int y = (i < lb) ? b[i] : 0;
        if (x < y) { x += 10; borrow = 1; }   // 不够减则借 10
        else borrow = 0;
        c[i] = x - y;
    }
    int lc = la;
    while (lc > 1 && c[lc - 1] == 0) lc--;   // 去掉前导 0（至少留 1 位）
    return lc;
}

五、高精度乘法

模拟竖式：c[i+j] += a[i] * b[j]，最后统一处理进位。

C++ 实例

// 高精度乘法 a × b -> c，返回位数（竖式乘法：i 位 × j 位 加到 i+j 位）
int mul(int a[], int la, int b[], int lb, int c[]) {
    for (int i = 0; i < la; i++) {
        for (int j = 0; j < lb; j++) {
            c[i + j] += a[i] * b[j];   // 先累加，不急着进位
        }
    }
    int lc = la + lb;
    for (int i = 0; i < lc; i++) {       // 最后统一进位
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    while (lc > 1 && c[lc - 1] == 0) lc--;   // 去前导 0
    return lc;
}

用高精度求大数阶乘（经典例题）

C++ 实例

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    int a[1000] = {1};           // 存积，初始为 1
    int len = 1;                 // 当前位数
    for (int i = 2; i <= n; i++) {      // 依次乘 2..n
        int carry = 0;                  // 进位
        for (int j = 0; j < len; j++) { // 逐位乘 i 并处理进位
            int t = a[j] * i + carry;
            a[j] = t % 10;              // 当前位
            carry = t / 10;             // 新进位
        }
        while (carry) {                 // 进位延伸到新位
            a[len++] = carry % 10;
            carry /= 10;
        }
    }
    for (int i = len - 1; i >= 0; i--) cout << a[i];
    cout << endl;   // n! 的结果（如 20! = 2432902008176640000）
    return 0;
}

形象理解乘法像竖式乘法的展开：第 i 位 × 第 j 位的结果写到 c[i+j]，全部乘完再统一进位——和加法边加边进位不同。

易错点乘法两坑：① 结果数组长度要开 la + lb，开小了越界；② c[i+j] += a[i] * b[j] 中间值可能很大，用 int 存时注意或压位（万进制）防溢出。

六、高精度除法（进阶）

高精度除以低精度（单精度）：从高位到低位逐位 "除 + 取余"；高精度除以高精度用"减法模拟"/倍增法（NOIP 才常考）。

C++ 实例

// 高精度除以 int：从最高位开始逐位除（竖式除法）
int divSmall(int a[], int len, int b, int q[], int &rem) {
    rem = 0;                        // 余数（引用传出）
    int lq = 0;                     // 商的位数
    for (int i = len - 1; i >= 0; i--) {   // 从高位往低位
        rem = rem * 10 + a[i];      // 余数补位 + 当前位
        q[lq++] = rem / b;          // 商的一位
        rem %= b;                   // 更新余数
    }
    // 去掉前导 0（此片段略，完整实现需处理 lq 起始位置）
    return lq;
}

七、易错点 / 常见坑点

⚠️ 倒序存储与输出方向记反（存个位在 0 号，输出倒序）。
⚠️ 加法进位 carry 在最高位单独处理；乘法要全部算完再统一进位。
⚠️ 减法要先 cmp 保证大减小，并去前导 0。
⚠️ 乘积数组开小（需要 la+lb 长度），越界。
⚠️ long long 溢出的乘法里 c[i+j] += a[i]*b[j] 本身就可能超过 int，需用大类型存或压位。
⚠️ 忘记 memset 清零、初始化 a[0]=0 或 =1 的起始值。
⚠️ 阶乘中 carry 的位数累加进位处理不当。

八、考级要求 vs 竞赛进阶

考级要求（GESP 5 级）：高精度加法为典型考点（数组模拟加法）；减法/乘法在部分卷中出现（思路考查为主）。
竞赛进阶（CSP-J/NOIP）：高精度乘/除、压位优化、大数应用（卡特兰数、超大组合数）、高精度与 DP/数论结合。

九、课内练习建议

用高精度计算 123456789012345678 + 987654321098765432。
手写高精度乘法并输出 25^20 的精确值。
用高精度求 50! 并验证位数。
实现高精度除以单精度并求余数。
尝试"万进制压位"优化一个 1000 位相加。