XZXZZXBlog

Article

高精度

数字大到内置类型装不下时，就不能直接用 int 或 long long 算了。

约 6 分钟

文章目录

高精度的核心场景只有一句话：

  • 数字大到内置类型装不下时，就不能直接用 int / long long 算了。

竞赛里最常见的是：

  • 高精度加法
  • 高精度减法
  • 高精度乘法
  • 高精度除法（通常是高精度除以低精度）

1. 高精度的统一表示方法

最常见写法是：

  • 用 string 读入
  • 把每一位数字拆出来
  • 倒序存到 vector<int> 里

例如：

Text
12345

存成：

Text
[5, 4, 3, 2, 1]

这样做的好处是：

  • 个位在下标 0
  • 十位在下标 1
  • 进位、借位、乘法竖式都更顺手

常用读入模板：

C++
vector<int> A;
string a;
cin >> a;
for (int i = a.size() - 1; i >= 0; --i) {
    A.push_back(a[i] - '0');
}

输出时反着打印：

C++
for (int i = C.size() - 1; i >= 0; --i) {
    cout << C[i];
}

2. 高精度加法

2.1 核心思路

和小学竖式加法完全一样：

  • 对应位相加
  • 维护进位 carry
  • 最后如果还有进位，再补一位

2.2 模板

C++
vector<int> add(vector<int> &A, vector<int> &B) {
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;

    for (int i = 0; i < (int)A.size(); ++i) {
        t += A[i];
        if (i < (int)B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

2.3 你该记住什么

  • 长的和短的对齐，短的越界部分按 0 算
  • t % 10 是当前位
  • t / 10 是进位

3. 高精度减法

3.1 核心思路

高精度减法通常默认写成：

  • 先保证 A >= B
  • 计算 A - B
  • 如果原来是小数减大数，就先输出负号，再算 B - A

3.2 比较函数

C++
bool cmp(vector<int> &A, vector<int> &B) {
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; --i) {
        if (A[i] != B[i]) return A[i] > B[i];
    }
    return true;
}

3.3 模板

C++
vector<int> sub(vector<int> &A, vector<int> &B) {
    vector<int> C;
    int t = 0;

    for (int i = 0; i < (int)A.size(); ++i) {
        t = A[i] - t;
        if (i < (int)B.size()) t -= B[i];

        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

3.4 你该记住什么

  • t 在这里表示“是否借位”
  • 最后一定要去掉前导零
  • 结果如果是 0，要保留一个 0

4. 高精度乘法

高精度乘法常见两种：

  • 高精度乘低精度
  • 高精度乘高精度

4.1 高精度乘低精度

这是最常用、也最简单的一种。

模板

C++
vector<int> mul(vector<int> &A, int b) {
    vector<int> C;
    int t = 0;

    for (int i = 0; i < (int)A.size() || t; ++i) {
        if (i < (int)A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

你该记住什么

  • 这一题型经常出在阶乘、幂、递推累乘
  • 本质上还是竖式乘法

4.2 高精度乘高精度

这是完全版乘法。

核心思路

  • A[i] * B[j] 会贡献到结果的第 i + j 位
  • 先全部累加
  • 再统一处理进位

模板

C++
vector<int> mul(vector<int> &A, vector<int> &B) {
    vector<int> C(A.size() + B.size(), 0);

    for (int i = 0; i < (int)A.size(); ++i) {
        for (int j = 0; j < (int)B.size(); ++j) {
            C[i + j] += A[i] * B[j];
        }
    }

    int t = 0;
    for (int i = 0; i < (int)C.size(); ++i) {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

你该记住什么

  • 乘法结果数组长度最多是两数长度之和
  • i + j 这个位置映射一定要记熟

5. 高精度除法

竞赛里最常见的是：

  • 高精度 ÷ 低精度

高精度除高精度比较少见，通常不作为基础模板要求。

5.1 核心思路

和手算长除法一样：

  • 从高位往低位扫
  • 当前余数乘 10 再加当前位
  • 商的当前位就是 余数 / b
  • 余数更新成 余数 % b

注意：

  • 加减乘通常因为倒序存储而从低位往高位算
  • 除法是从高位往低位算

5.2 模板

C++
vector<int> div(vector<int> &A, int b, int &r) {
    vector<int> C;
    r = 0;

    for (int i = A.size() - 1; i >= 0; --i) {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }

    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

5.3 你该记住什么

  • 商和余数一起算
  • 先从高位开始
  • 因为我们的原数是倒序存的，所以循环方向要反过来
  • 最后 reverse 一次，才能继续保持“倒序存储”的统一格式

6. 四种运算最容易混的点

6.1 为什么加减乘大多从低位开始，而除法从高位开始

  • 加法：进位往高位传
  • 减法：借位往高位传
  • 乘法：结果位数和 i+j 有关，天然适合低位起算
  • 除法：长除法必须从高位往低位推进

6.2 为什么总是要“去前导零”

因为算完以后可能出现：

Text
00123
0000

都需要规整成：

Text
123
0

常用写法：

C++
while (C.size() > 1 && C.back() == 0) C.pop_back();

6.3 为什么高精度喜欢用 vector<int>

因为：

  • 动态长度方便
  • 单独处理每一位方便
  • 和模板结合自然

7. 一套统一的主函数写法

下面这个框架基本能套所有高精度题：

C++
string a, b;
cin >> a >> b;

vector<int> A, B;
for (int i = a.size() - 1; i >= 0; --i) A.push_back(a[i] - '0');
for (int i = b.size() - 1; i >= 0; --i) B.push_back(b[i] - '0');

auto C = add(A, B);  // 或 sub / mul

for (int i = C.size() - 1; i >= 0; --i) cout << C[i];
cout << '\n';

8. 什么时候该想到高精度

看到这些特征就要警觉：

  • 输入是特别长的整数
  • 数字位数远超 long long
  • 求大数阶乘
  • 求大整数幂
  • 明确写着“高精度”
  • 结果位数会爆内置类型

比如：

  • 1000!
  • 2^10000
  • 两个几百位整数相乘

9. 高频坑点

9.1 忘了倒序存

这是最常见错误。

  • 如果不倒序，进位借位会很难写

9.2 忘了去前导零

尤其减法和除法很容易出这个问题。

9.3 负号处理不完整

减法里要先比较大小：

  • 如果 A < B，先输出 -
  • 再算 B - A

9.4 除法方向写反

高精度除法必须从高位往低位扫。

9.5 结果数组开得太小

乘法里结果长度最多是：

Text
A.size() + B.size()

别少开。

10. 四种运算怎么背

10.1 加法

  • 对位相加
  • 处理进位

10.2 减法

  • 先比大小
  • 对位相减
  • 处理借位

10.3 乘法

  • 每位两两相乘
  • 扔到 i + j
  • 最后统一进位

10.4 除法

  • 从高位往低位
  • 维护余数
  • 得到商和余数

11. 最小必背清单

如果考前只看一分钟，就背这些：

11.1 表示方式

  • string 读入
  • vector<int> 存每一位
  • 倒序存储

11.2 四个关键点

  • 加法：进位
  • 减法：借位
  • 乘法：i + j
  • 除法：从高位往低位扫

11.3 去前导零

C++
while (C.size() > 1 && C.back() == 0) C.pop_back();

12. 一句话总结

高精度其实不难，核心就是：

  • 统一表示
  • 按小学竖式模拟
  • 把进位、借位、位数方向写清楚

只要你把“倒序存储 + 加减乘除四个模板”真正写熟，高精度这块就基本稳了。