HDU 1002 A + B Problem II：大整數加法模擬詳解

題目核心難點

• 整數長度 ≤ 1000 位，遠超 32/64 位整數範圍
• 多測試用例 (T ≤ 20)，需格式化輸出 "Case #:" 及 "A + B = Sum"
• 結果可能比輸入更長 (最高位進位)

算法思想：豎式加法模擬

1. 字符串讀入：用 char a[1001], b[1001] 存儲原始數字串
2. 逆序存入數組：個位放索引 1，十位放索引 2... 便於對齊相加
3. 逐位相加 + 進位：sum[i] = a[i] + b[i] + carry
4. 逆序輸出：從最高非零位向下打印

關鍵實現細節

1. 數組初始化

每輪循環必須 memset 或迴圈清零 a2, b2, sum，否則殘留數據導致錯誤 (原作者曾因此調試半小時)。

2. 字符轉數字

for (j = la-1, r = 1; j >= 0; j--, r++) a2[r] = a1[j] - '0';

減去 '0' (ASCII 48) 比寫死 48 可讀性強。

3. 進位處理

for (j = 1; j <= k; j++) {
    sum[j] += a2[j] + b2[j];
    if (sum[j] >= 10) {
        sum[j] -= 10;
        sum[j+1]++; // 向高位進位
    }
}

注意：最高位進位可能導致結果長度 k+1，輸出前需檢查 sum[k+1]。

4. 輸出格式控制

• Case 編號從 1 開始
• 兩 Case 間空一行 (最後一個 Case 後不空行)
• 原始輸入可能有前導零？題目說「正整數」通常無前導零，但輸出時需確保不輸出前導零 (逆序打印自然滿足)

完整優化代碼 (C99)

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

#define MAXL 1005

int main() {
    int T;
    scanf("%d", &T);
    for (int tc = 1; tc <= T; tc++) {
        char s1[MAXL], s2[MAXL];
        int a[MAXL] = {0}, b[MAXL] = {0}, sum[MAXL] = {0};
        scanf("%s %s", s1, s2);
        int la = strlen(s1), lb = strlen(s2);
        // 逆序存儲
        for (int i = 0; i < la; i++) a[i+1] = s1[la-1-i] - '0';
        for (int i = 0; i < lb; i++) b[i+1] = s2[lb-1-i] - '0';
        int k = (la > lb ? la : lb);
        // 逐位相加
        for (int i = 1; i <= k; i++) {
            sum[i] += a[i] + b[i];
            if (sum[i] >= 10) {
                sum[i] -= 10;
                sum[i+1]++;
            }
        }
        if (sum[k+1]) k++; // 處理最高位進位
        // 輸出
        printf("Case %d:\n", tc);
        for (int i = la; i >= 1; i--) putchar(a[i] + '0');
        printf(" + ");
        for (int i = lb; i >= 1; i--) putchar(b[i] + '0');
        printf(" = ");
        for (int i = k; i >= 1; i--) putchar(sum[i] + '0');
        printf("\n");
        if (tc != T) printf("\n");
    }
    return 0;
}

避坑清單

1. 數組大小定義 > 1000 (如 1005) 防越界
2. 每輪循環完全清零所有工作數組
3. 輸出時逆序遍歷數組下標
4. 判斷最高位進位 sum[k+1]
5. Case 間空行邏輯：if (tc != T) puts("");
6. 輸入用 %s 直接讀字符串，避免 scanf 空白字符困擾

延伸：C++ 版本 (高精度模板)

C++ 可用 std::string + reverse_iterator 或現成 BigInteger 庫，代碼更簡潔安全。但 ACM 競賽常要求純 C 實現，掌握數組模擬是基本功。

總結

HDU 1002 是「大整數加法」的標準入門題。核心是「字符串存儲、逆序對齊、逐位運算、進位傳遞、逆序輸出」五步曲。細節決定成敗：初始化、邊界、格式。熟練掌握此模板，後續大整數減法、乘法、除法、階乘、斐波那契皆可類推。