HDU 1002 A+B Problem II 大整數加法詳解：字符串模擬逐位相加

HDU 1002將A+B Problem擴展到超長整數（長度≤1000位），標準整數類型無法存儲，必須用字符串模擬手工列豎加法。本文完整解析算法邏輯、代碼實現細節與關鍵避坑點。

題目要求

• 輸入：第一行T(1≤T≤20)測試組數，隨後T行每行兩個正整數A、B
• 長度：每個整數長度≤1000位
• 輸出：每組兩行，Case #: 和 A + B = Sum，組間空行
• 樣例：112233445566778899 + 998877665544332211 = 1111111111111111110

算法核心：字符串模擬列豎加法

步驟流程

1. 字符串讀入：用char數組讀取大整數（scanf("%s")）
2. 逆序存儲：將字符轉為int數字，按個位在下標1存儲（方便進位）
3. 逐位相加：從低位向高位，對應位相加+進位，模10得當前位，除10得進位
4. 處理最高位進位：最終可能產生新的最高位
5. 逆序輸出：從高位向低位打印

關鍵數據結構

char a1[1001], b1[1001];  // 原始字符串，+1存\0
int a2[1001], b2[1001];   // 逆序數字數組，下標1開始
int sum[1001];            // 結果數組

數組大小1001：題目≤1000位，+1防越界，+1存\0，實際1005更保險。

完整代碼走讀

#include <stdio.h>
#include <string.h>

int main() {
    char a1[1001], b1[1001];
    int a2[1001], b2[1001], sum[1001];
    int n, i = 1;
    
    scanf("%d", &n);
    while (i <= n) {
        // 1. 數組歸零初始化 —— 關鍵！多測試用例必須每輪清零
        for (int j = 0; j < 1001; j++) 
            a2[j] = b2[j] = sum[j] = 0;
        
        // 2. 讀入字符串
        scanf("%s %s", a1, b1);
        int la = strlen(a1), lb = strlen(b1);
        
        // 3. 字符轉數字並逆序存儲
        int r = 1;
        for (int j = la - 1; j >= 0; j--) 
            a2[r++] = a1[j] - '0';  // '0'=48，比寫48可讀
        r = 1;
        for (int j = lb - 1; j >= 0; j--) 
            b2[r++] = b1[j] - '0';
        
        // 4. 逐位相加
        int k = (la > lb) ? la : lb;  // 以較長長度為準
        for (int j = 1; j <= k; j++) {
            sum[j] += a2[j] + b2[j];
            if (sum[j] >= 10) {       // 進位
                sum[j] -= 10;
                sum[j + 1]++;         // 向高位進1
            }
        }
        
        // 5. 輸出結果
        printf("Case %d:\n", i);
        for (int j = la; j >= 1; j--) printf("%d", a2[j]);
        printf(" + ");
        for (int j = lb; j >= 1; j--) printf("%d", b2[j]);
        printf(" = ");
        if (sum[k + 1]) k++;          // 檢查最高位進位
        for (int j = k; j >= 1; j--) printf("%d", sum[j]);
        printf("\n");
        if (i < n) printf("\n");      // 組間空行
        i++;
    }
    return 0;
}

關鍵避坑點總結

算法複雜度分析

• 時間：O(T × max(Lₐ, L_b))，L為數字長度，線性於位數
• 空間：O(max(Lₐ, L_b))，三個int數組
• T≤20，L≤1000，極限操作約20,000次，瞬時完成

進階優化與擴展

C++ string 版本（更安全、簡潔）

#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, 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 s = da + db + carry;
        res.push_back('0' + s % 10);
        carry = s / 10;
    }
    if (carry) res.push_back('0' + carry);
    reverse(res.begin(), res.end());
    return res;
}

大整數乘法/除法/模運算

• 乘法：模擬列豎乘法 O(N²)，或FFT/NTT O(N log N)
• 除法：模擬長除法，試商+減法
• 推薦成熟庫：GMP、Boost.Multiprecision/cpp_int、Java BigInteger

總結

HDU 1002是大整數運算的入門經典，核心思想：字符串存儲 → 逆序數字數組 → 逐位運算+進位 → 逆序輸出。掌握此模式，可擴展解決大整數減法、乘法、階乘、斐波那契等經典問題。關鍵在於細節：初始化、進位邊界、輸出順序、格式控制。