练78.2 大整数减法

解题思路

从个位起用被减数位减减数位和借位，不足0就加10并向更高位借1。结果逆序后去最高零。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

已保证a>b，不需负号；借位须传到下一位。

复杂度

最大D位，时间O(D)，空间O(D)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a, b;
    cin >> a >> b;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    string s;
    int borrow = 0;
    for (size_t i = 0; i < a.size(); i++) {
        int v = a[i] - '0' - borrow - (i < b.size() ? b[i] - '0' : 0);
        borrow = v < 0;
        if (borrow)
            v += 10;
        s += char('0' + v);
    }
    while (s.size() > 1 && s.back() == '0')
        s.pop_back();
    reverse(s.begin(), s.end());
    cout << s << "\n";
    return 0;
}