高精度运算
一句话定义:高精度就是把大数一位一位存进数组,像列竖式那样慢慢算,这样就突破了
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,四个都对上了再往下写。