高精度运算

一句话定义:高精度就是把大数一位一位存进数组,像列竖式那样慢慢算,这样就突破了 long long 只能存 19 位的限制。
记住三件事:倒着存、从个位开始算、算完把前面的 0 去掉。


一、为什么需要高精度

C++ 自带的整数类型都有上限:

类型 最多几位 大约上限
int 10 位 2.1 × 10⁹
unsigned int 10 位 4.3 × 10⁹
long long 19 位 9.2 × 10¹⁸
unsigned long long 20 位 1.8 × 10¹⁹

题目一旦让你算 100 的阶乘、2 的 1000 次方、两个 50 位数相加,这些类型全都不够用。

而 100! 有多少位?158 位。long long 只能存 19 位,差得远。

办法很朴素:把大数当成一串数字存进数组,像小学竖式那样一位一位算。

💡 想想你在纸上算 987654321 × 123:先乘个位,再乘十位、百位,最后错位加起来。高精度就是把这个过程翻译成代码。


二、准备三个数组

2.1 三个大数和三个长度

const int N = 500;              // 数组最多装 500 位

int a[N], b[N], c[N];           // 三个大数:a、b 放题目给的数,c 放结果
int la, lb, lc;                 // 每个数各有几位

约定一条:a[0] 存个位,a[1] 存十位,a[2] 存百位……越往后位越高。

这样存的好处是:进位只需要往"下一个位置"走,正好和代码里的 i + 1 对上。

2.2 读入:把数字倒着放

输入进来是一串字符,比如 "2025",我们想存成 a[0]=5, a[1]=2, a[2]=0, a[3]=2:

string s, t;
cin >> s >> t;

la = s.size();
for (int i = 0; i < la; i++) a[i] = s[la - 1 - i] - '0';

lb = t.size();
for (int i = 0; i < lb; i++) b[i] = t[lb - 1 - i] - '0';

两个小地方:

  • s[la - 1 - i]:当 i = 0 时取的是 s[la-1],也就是最后一位(个位);
  • - '0':把字符 '5' 变成数字 5,不减的话存进去是 ASCII 码 53。

2.3 输出:再倒着取回来

for (int i = lc - 1; i >= 0; i--) cout << c[i];
cout << "\n";

存的时候从个位进,输出的时候从最高位出,一进一出正好对上。

2.4 N 要开多大

要算的东西 结果多少位 N 至少开
100 位数加减 101 位 500
100! 158 位 500
1000! 2568 位 3000
两个 1000 位数相乘 2000 位 2100

乘法最费地方:两个 n 位数相乘,结果最多 2n 位。


三、加法

竖式加法就三步:对齐、每一位相加、满十进一。

void add() {                       // c = a + b
    int carry = 0;                 // 进位
    lc = max(la, lb);              // 位数取多的那个
    for (int i = 0; i < lc; i++) {
        int t = carry;
        if (i < la) t += a[i];
        if (i < lb) t += b[i];
        c[i] = t % 10;             // 这一位留个位
        carry = t / 10;            // 十位进给下一位
    }
    if (carry > 0) {               // 最高位还能再进一位
        c[lc] = carry;
        lc++;
    }
}
     987654321
   + 123456789
   -----------
    1111111110

最后那个 if 不能少:999 + 1 = 1000,位数从 3 位变成 4 位。


四、减法

4.1 先比大小

减法得"大的减小的",不然会借出负数。所以先写一个比较函数:

int cmp() {                        // a 大返回 1,相等返回 0,a 小返回 -1
    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;
}

4.2 逐位相减,不够就借

void sub() {                       // 要求 a >= b
    int borrow = 0;                // 借位
    lc = la;
    for (int i = 0; i < lc; i++) {
        int t = a[i] - borrow;
        if (i < lb) t -= b[i];
        if (t < 0) {               // 不够减,向高位借一当十
            t += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        c[i] = t;
    }
    while (lc > 1 && c[lc - 1] == 0) lc--;      // 去掉前面的 0
}

1000000000 - 1 会一路借到底,位数从 10 位缩成 9 位:

    1000000000
   -         1
   -----------
     999999999

如果 a 比 b 小,就先交换再减,最后补一个负号:

if (cmp() < 0) {
    for (int i = 0; i < N; i++) swap(a[i], b[i]);
    swap(la, lb);
    cout << "-";
}
sub();

⚠️ 加法的位数会变多,减法的位数会变少,这两句话记牢,写循环边界时就不会错。


五、乘法

5.1 高精度 × 一个普通整数

比如算阶乘时要不断乘 2、3、4……这种情况不用竖式,一位一位乘过去就行,结果直接改回 a 自己:

void mulSmall(int k) {             // a = a * k
    int carry = 0;
    for (int i = 0; i < la; i++) {
        int t = a[i] * k + carry;
        a[i] = t % 10;
        carry = t / 10;
    }
    while (carry > 0) {            // 剩下的进位一位一位写进去
        a[la] = carry % 10;
        carry = carry / 10;
        la++;
    }
}

5.2 高精度 × 高精度

两个大数相乘,先把所有"位对位"的乘积累加,最后统一处理进位:

void mul() {                       // c = a * b
    lc = la + lb;                  // 结果最多这么多位
    for (int i = 0; i < lc; i++) c[i] = 0;

    for (int i = 0; i < la; i++)
        for (int j = 0; j < lb; j++)
            c[i + j] += a[i] * b[j];       // 错位累加

    int carry = 0;
    for (int i = 0; i < lc; i++) {         // 最后统一进位
        c[i] += carry;
        carry = c[i] / 10;
        c[i] %= 10;
    }
    while (lc > 1 && c[lc - 1] == 0) lc--;
}

为什么是 c[i + j]?看竖式就明白了:

        1 2 3
   ×      4 5
   -----------
        6 1 5        ← 123 的每一位乘 5,落在原位置
      4 9 2          ← 123 的每一位乘 4,整体往左挪一位
   -----------
      5 5 3 5

a 的第 i 位乘 b 的第 j 位,结果的"位权"是 i + j,所以加到 c[i + j] 上。

⚠️ lc 一开始要按 la + lb 算。99 × 99 = 9801 已经是 4 位,比两个乘数都多一位。

这里用了两重循环,位数越多越慢。1000 位的两个数相乘,就要做大约一百万次加法。


六、除法

除以一个普通整数(比如除以 7、除以 100),从最高位开始:

int rem;                           // 余数

void divSmall(int d) {             // c = a / d,余数放进 rem
    long long r = 0;
    lc = la;
    for (int i = la - 1; i >= 0; i--) {     // 注意:从高位往低位
        r = r * 10 + a[i];                  // 把这一位"落"下来
        c[i] = r / d;                       // 这一位的商
        r = r % d;                          // 剩下的余数
    }
    rem = r;
    while (lc > 1 && c[lc - 1] == 0) lc--;
}

拿 987654321 ÷ 7 走一遍,就能看清这个过程:

落下来的位 变成的数 这一位的商 剩下的余数
9 9 1 2
8 28 4 0
7 7 1 0
6 6 0 6
5 65 9 2
4 24 3 3
3 33 4 5
2 52 7 3
1 31 4 3

商是 141093474,余 3。

注意它和加法的方向正好相反:加法从个位往高位走,除法必须从高位往低位走。

💡 除以另一个大数怎么办?办法还是竖式:每确定一位商,就从 9 往下试,看"除数 × 试商"有没有超过当前余数。这一步要反复用乘法和减法,代码比较长,先把上面这种"除以普通整数"练熟。

⚠️ 余数 r 用 long long 存,别用 int:除数接近 10 亿时,r * 10 会超出 int 的范围。


七、实战:算 100!

100! 是 1 × 2 × 3 × … × 100,用上面的 mulSmall 一遍遍乘就行。这是一个可以完整运行的程序:

#include <iostream>
using namespace std;

const int N = 500;

int a[N];
int la = 1;                        // 一开始 a = 1

void mulSmall(int k) {             // a = a * k
    int carry = 0;
    for (int i = 0; i < la; i++) {
        int t = a[i] * k + carry;
        a[i] = t % 10;
        carry = t / 10;
    }
    while (carry > 0) {
        a[la] = carry % 10;
        carry = carry / 10;
        la++;
    }
}

int main() {
    a[0] = 1;
    for (int i = 2; i <= 100; i++)
        mulSmall(i);               // 依次乘 2、3、…、100

    cout << la << " 位数\n";       // 158
    for (int i = la - 1; i >= 0; i--)
        cout << a[i];
    cout << "\n";
    return 0;
}

输出:

158 位数
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

小检查:末尾有 24 个 0(每凑出一个 2×5 就多一个 0),位数 158。这两个数都能帮你判断算得对不对。

💡 想把 100 换成 1000 试试?记得把 N 调到 3000 以上,否则数组装不下。


八、自测七题

先自己答,再看右边。

题号 题目 答案
1 long long 最多能存几位十进制数? 19 位
2 数组里 a[0] 存的是哪一位? 个位
3 123456789 + 987654321 等于多少? 1111111110
4 两个 n 位数相乘,结果最多几位? 2n 位
5 高精度除法从哪一位开始算? 最高位
6 100! 末尾有几个 0? 24 个
7 做减法之前必须先做什么? 比较大小,保证大减小

总结

💡 全文一句话:三个数组、三个长度,倒着存、正着算,进位借位别忘,最后去掉前面的 0。

  • 存:a[0] 是个位,la 记位数,位数至少是 1
  • 读入倒着放,输出倒着取
  • 加法:逐位加,满十进一,位数可能变多
  • 减法:先用 cmp() 比大小,不够就借一当十,位数可能变少
  • 乘法:高 × 低走一遍;高 × 高先累加到 c[i+j],再统一进位
  • 除法:从高位开始,边乘 10 边留余数,商写 c[i]

⚠️ 最后一记警钟:高精度写错从来不报错——数组开小一格、少存一位、漏借一位,程序照样跑完,只是答案差一个数字。写完一定拿小例子手算对一遍:99 + 1、1000 - 1、99 × 99、987654321 ÷ 7,四个都对上了再往下写。


本站由 奇迹欧埃 使用 Stellar 创建。