HDU 1002 大數加法完整解析

題目要求計算兩個超長整數（長度 ≤ 1000 位）的和，測試資料最多 20 組。標準 32/64 位整數無法儲存，必須採用字串或陣列模擬手算加法。

核心演算法：模擬豎式加法

將兩數字串反轉或從尾部向前遍歷，逐位相加並處理進位：

1. 字串長度可能不同，短者視為高位補 0
2. 每位相加：sum = a[i] + b[i] + carry
3. 當前位結果：sum % 10，進位：sum / 10
4. 最高位若有進位需額外輸出

完整 AC 程式碼（C 語言）

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

char a[1001], b[1001], c[1002];

int main() {
    int T;
    scanf("%d", &T);
    
    for (int case_num = 1; case_num <= T; case_num++) {
        scanf("%s %s", a, b);
        
        int lena = strlen(a), lenb = strlen(b);
        int carry = 0, idx = 0;
        
        // 從個位開始逐位相加
        for (int i = lena - 1, j = lenb - 1; i >= 0 || j >= 0; i--, j--, idx++) {
            int da = (i >= 0) ? a[i] - '0' : 0;
            int db = (j >= 0) ? b[j] - '0' : 0;
            int sum = da + db + carry;
            c[idx] = (sum % 10) + '0';
            carry = sum / 10;
        }
        
        // 處理最高位進位
        if (carry) c[idx++] = carry + '0';
        c[idx] = '\0';
        
        // 結果需反轉輸出
        printf("Case %d:\n", case_num);
        printf("%s + %s = ", a, b);
        for (int i = idx - 1; i >= 0; i--) putchar(c[i]);
        printf("\n");
        if (case_num != T) printf("\n"); // 兩測資間空一行
    }
    return 0;
}

關鍵細節說明

• 字串長度 1000：陣列需開 ≥ 1001，結果最多 1001 位（含進位）
• 輸出格式嚴格：Case #: 獨佔一行，算式第二行，測資間空行
• 前導零處理：輸入無前導零，輸出亦不應有（最高位進位除外）
• 效能考量：O(N) 時間複雜度，N=1000 瞬間完成

進階優化方向

若需進一步優化，可考慮：

• 每次處理 4 位（基數 10000），減少迴圈次數 4 倍
• 使用 int 陣列儲存數字而非字元，避免字元轉換開銷
• C++ 可用 std::string 或 vector<int> 簡化記憶體管理