高精度算法详解：大整数加减乘除实现与原理

注意：这里逆序存储是为了让数组下标 0 对应个位，这样进位可以直接加到 i+1 位置，符合自然计算习惯。

三、高精度减法

题目背景

计算 A - B，需确保被减数大于等于减数。

实现细节

1. 比较大小：先比较位数，位数相同则按字典序比较。
2. 借位处理：若某一位不够减，向高位借 1 当 10。
3. 前导零：结果可能产生前导零，需去除。

#include<iostream>
using namespace std;

const int N = 1e6 + 10;
int a[N], b[N], c[N];
string x, y;
int la, lb, lc;

bool cmp(string& x, string& y) {
    if (x.size() != y.size()) return x.size() < y.size();
    return x < y;
}

void sub(int c[], int a[], int b[]) {
    for (int i = 0; i < lc; i++) {
        c[i] += a[i] - b[i];
        if (c[i] < 0) {
            c[i + 1] -= 1;  // 向高位借位
            c[i] += 10;
        }
    }
    while (lc > 1 && c[lc - 1] == 0) lc--; // 去除前导零
}

int main() {
    cin >> x >> y;
    if (cmp(x, y)) {
        swap(x, y);
        cout << '-';
    }
    la = x.size();
    lb = y.size();
    lc = max(la, lb);
    
    for (int i = 0; i < la; i++) a[la - i - 1] = x[i] - '0';
    for (int i = 0; i < lb; i++) b[lb - i - 1] = y[i] - '0';
    
    sub(c, a, b);
    for (int i = lc - 1; i >= 0; i--) cout << c[i];
    return 0;
}

四、高精度乘法

题目背景

计算 A * B，通常涉及一个大整数乘以另一个大整数。

实现细节

采用'无进位相乘再统一进位'的策略，类似竖式乘法中每一行错位累加的过程。

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N], b[N], c[N];
string x, y;
int la, lb, lc;

void mul(int c[], int a[], int b[]) {
    // 无进位相乘，然后相加
    for (int i = 0; i < la; i++) {
        for (int j = 0; j < lb; j++)
            c[i + j] += a[i] * b[j];
    }
    
    // 统一处理进位
    for (int i = 0; i < lc; i++) {
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    
    while (lc > 1 && c[lc - 1] == 0) lc--;
}

int main() {
    cin >> x >> y;
    la = x.size();
    lb = y.size();
    lc = la + lb;
    
    for (int i = 0; i < la; i++) a[la - i - 1] = x[i] - '0';
    for (int i = 0; i < lb; i++) b[lb - i - 1] = y[i] - '0';
    
    mul(c, a, b);
    for (int i = lc - 1; i >= 0; i--) cout << c[i];
    return 0;
}

五、高精度除法

题目背景

此处特指「高精度除以低精度」，即大整数除以普通整数。

实现细节

模拟手算除法，从高位到低位逐位试商。

#include<iostream>
using namespace std;

const int N = 1e6 + 10;
typedef long long LL;
int a[N], b, c[N];
string x;
int la;

void div(int c[], int a[], int b) {
    LL t = 0;
    for (int i = la - 1; i >= 0; i--) {
        t = t * 10 + a[i];      // 当前被除数
        c[i] = t / b;           // 记录商
        t %= b;                 // 余数留给下一位
    }
    while (la > 1 && c[la - 1] == 0) la--; // 去除前导零
}

int main() {
    cin >> x >> b;
    la = x.size();
    for (int i = 0; i < la; i++) a[la - i - 1] = x[i] - '0';
    
    div(c, a, b);
    for (int i = la - 1; i >= 0; i--) cout << c[i];
    return 0;
}

总结

高精度算法的核心在于将大数拆解为数组元素，通过模拟人工计算流程来突破数据类型限制。关键点包括：

• 存储方式：逆序存储便于进位和借位操作。
• 边界处理：务必检查前导零和空值情况。
• 复杂度：通常为 O(N)，N 为数字位数。

掌握这些模板后，面对大数运算问题即可从容应对。