SOJ 1002 大數加法 詳解

題目：輸入多行，每行兩個非負整數（以空格分隔），長度不超過 1000 位。輸出它們的和。數字可能有前導零。輸入以 EOF 結束。

核心算法：字符串反轉 + 逐位相加 + 進位

1. 讀取兩字符串 a, b。
2. 反轉或從末尾向前遍歷，對應位相加 + 進位 carry。
   sum = (a[i]-'0') + (b[j]-'0') + carry，
   結果位 sum % 10，新進位 sum / 10。
3. 較長字符串剩餘位繼續加進位。
4. 最終若 carry>0 補上。
5. 結果反轉，去除前導零（但至少保留一位 0）。

關鍵邊界情況（坑點）

參考代碼 (C++)

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

string addStrings(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    string res;
    int carry = 0;
    int n = max(a.size(), b.size());
    for (int i = 0; i < n; ++i) {
        int da = (i < a.size()) ? a[i] - '0' : 0;
        int db = (i < b.size()) ? b[i] - '0' : 0;
        int sum = da + db + carry;
        res.push_back('0' + (sum % 10));
        carry = sum / 10;
    }
    if (carry) res.push_back('0' + carry);
    reverse(res.begin(), res.end());
    // 去除前導零
    int pos = 0;
    while (pos + 1 < res.size() && res[pos] == '0') ++pos;
    return res.substr(pos);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a, b;
    while (cin >> a >> b) {
        cout << addStrings(a, b) << '\n';
    }
    return 0;
}

輸入讀取細節

題目輸入格式：每行兩數，以空格分隔。用 cin >> a >> b 可自動跳過空白（含換行），完美適配。若數字極長（>10⁵），需用 scanf 或快速 IO，但 1000 位 cin 關閉同步足夠。

複雜度分析

總結

SOJ 1002 是大數加法的入門模板題。核心考點：字符串反轉對齊、逐位加進位、前導零處理。此模板可直接擴展至大數減法（比較大小再減）、乘法（FFT/模擬）、除法。掌握邊界情況（全零、進位擴展、前導零輸入/輸出）是 AC 關鍵。