大整数减法——题解与思路

题目大意

题目要求我们计算两个很大的正整数相减的结果。这里的“大”是指数位很多，最多可以有 200 位，远远超出 int、long long 甚至 unsigned long long 能表示的范围，所以不能直接用普通整数类型来计算。

输入有两行：第一行是被减数 a，第二行是减数 b。题目保证 a > b，因此结果一定是正数，不会出现负数，也不会出现“小数减大数”的情况。同时两个数都是规整的，没有多余的、位于最前面的前导零。

输出只有一行，就是 a − b 的精确结果。

例如样例 1 中，一个 37 位左右的数减去一个 13 位的数，结果中间出现了一长串 0；样例 2 则是 100000000000000000000 − 1，结果是一串 9。这类题目的关键不在于数值大小，而在于“按位处理”的思想。

解题思路

第一步：为什么用字符串。 200 位的整数没有任何内置类型存得下，但每一位数字本质上是一个字符。把输入当成字符串读进来，就能完整保留每一位，这是高精度计算最基本的做法。

第二步：为什么翻转。 我们平时手算减法是从个位开始往左算的，而字符串的下标 0 对应的是最高位。为了方便“从低位往高位”逐位处理，先把两个字符串都翻转，这样下标 0 就是最低位（个位），下标 i 就对应第 i 位。

第三步：逐位相减并处理借位。 设当前正在处理第 i 位，被减数这一位是 da，减数这一位是 db（如果 b 已经比完了，就当作 0）。先算 d = da – db – borrow，其中 borrow 是上一位借过来的 1。

• 如果 d >= 0，这一位的结果就是 d，借位清零；
• • 如果 d < 0，说明不够减，要向前一位借 1，这一位的结果变成 d + 10，同时把借位标记设为 1。
    这里有个细节：因为题目保证 a > b，所以 b 的位数一定不超过 a。循环以 a 的长度为准，b 越界的位置补 0 就行，不会出现最后还欠着借位的情况。

第四步：去掉前导零。 逐位算完后，结果的最低位在 res 的下标 0 处。此时可能有形如 00123 的情况（比如 1000 − 997 = 3，算出来会是 3000 的翻转形式）。要去掉的是结果高位上的 0，也就是 res 末尾的 0。删除时要注意保留至少一位，否则结果为 0 时会输出空串。最后再把 res 翻转回来，就是正常的从高位到低位的写法。

参考代码（cpp）

// 1169 大整数减法
// 求两个大的正整数相减的差（a > b），均不超过200位，无前导0
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string subtract(string a, string b) {
// 题目保证 a > b
reverse(a.begin(), a.end()); // 翻转后下标0是个位
reverse(b.begin(), b.end());
string res;
int borrow = 0; // 借位标记
for (int i = 0; i < (int)a.size(); i++) {
int da = a[i] – '0';
int db = i < (int)b.size() ? b[i] – '0' : 0; // b 越界补 0
int d = da – db – borrow;
if (d < 0) {
d += 10;
borrow = 1; // 向高位借 1
} else {
borrow = 0;
}
res += char('0' + d); // 结果低位在前
}
// 去掉结果高位的多余 0，至少保留一位
while (res.size() > 1 && res[res.size() – 1] == '0') res.erase(res.size() – 1);
reverse(res.begin(), res.end()); // 翻回高位在前
return res;
}
int main() {
string a, b;
cin >> a >> b;
cout << subtract(a, b) << endl;
return 0;
}
```
## 易错点

**1. 借位没有在每一位都清零或置位。** 有的同学写成只在 `d < 0` 时设 borrow = 1，却忘了在 `d >= 0` 时把它改回 0，导致后面所有位都莫名其妙少 1。

**2. 前导零删错了方向。** 因为字符串翻转过了，高位的 0 在 res 的末尾，不在开头。如果去删 `res[0]`，删掉的是个位，答案直接错。

**3. 把结果删成空串。** 当 a 和 b 相等时（虽然本题保证 a > b，但自己改代码时容易遇到），结果是 0，删零循环如果不加 `res.size() > 1` 的保护，就会输出空行。养成“至少留一位”的习惯。

**4. 位数越界访问。** 循环用 b 的长度去跑，或者取 `b[i]` 时不判断 `i < b.size()`，都会越界。本题 b 一定比 a 短或等长，但循环条件必须按 a 的长度写。

**5. 字符与数字混用。** `a[i] – '0'` 才是数字，直接拿 `a[i]` 参与运算是拿 ASCII 码在算；最后拼回字符串时也要 `char('0' + d)`。

**6. 用 cin 读入后忘了这是字符串。** 千万别写 `int a; cin >> a;`，200 位的数一读就溢出，后面的逻辑再对也没用。

## 练习思考

如果把题目改成：输入两个正整数 a 和 b，**不保证 a > b**，要求输出 a − b 的差（结果可能为负）。你需要在现有代码上做哪些改动？

提示：先比较两个数的长度，长度相同再按字典序比较大小，确定谁减谁、结果是否带负号；减法部分可以完全复用上面的函数。请自己动手改一改，并用 `5 8`、`123 123`、`1000 999` 这样的数据检验。

—–

> 题目选自《信息学奥赛一本通》。本文题解由乐学谷教学团队编写。