【例78.2】大整数加法

解题思路

从两个数的最低位开始做竖式加法，每位加两数当前数字和进位，保存个位、向高位传十位。最终逆序并去多余前导零。

正确性说明

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

易错点

输入可能有前导零；最后还有进位要继续一轮。

复杂度

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

参考代码（C++11）

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

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