C語言階乘求和溢出：long long 不夠用時的三種應對策略

現象

long sum = 0;
for (int i = 1; i <= 10; i++) {
    long s = 1;
    for (int j = 1; j <= i; j++) s *= j;
    sum += s;
}
printf("%d", sum); // ❌ %d 對應 int，sum 是 long，且 10! 累加超過 2^31-1
// 輸出負數：溢出繞回

根本原因：數據類型範圍不足

原代碼用 long (Windows 下 4 字節) 且 printf("%d") 格式錯誤，導致輸出亂碼/負數。

修正代碼（long long + 正確格式）

#include 
#include  // PRIu64 跨平台格式宏

int main() {
    long long sum = 0;
    for (int i = 1; i <= 10; i++) {
        long long fact = 1;
        for (int j = 1; j <= i; j++) fact *= j;
        sum += fact;
        printf("%d! = %lld\n", i, fact);
    }
    printf("1!+2!+...+10! = %lld\n", sum); // 正確輸出 4037913
    return 0;
}

當 long long 也不夠時（如 20! 累加）三大策略

策略一：任意精度庫 —— GMP (GNU Multiple Precision)

// 需安裝 libgmp-dev，編譯加 -lgmp
#include 

int main() {
    mpz_t sum, fact;
    mpz_init_set_ui(sum, 0);
    mpz_init_set_ui(fact, 1);
    for (int i = 1; i <= 100; i++) {
        mpz_mul_ui(fact, fact, i); // fact *= i
        mpz_add(sum, sum, fact);   // sum += fact
        gmp_printf("%d! = %Zd\n", i, fact);
    }
    gmp_printf("Sum = %Zd\n", sum);
    mpz_clear(sum); mpz_clear(fact);
    return 0;
}

策略二：手寫大整數（數組模擬十進制/萬進制）

#define BASE 10000
#define WIDTH 4
int a[1000] = {1}; // 存儲階乘，低位在前
int sum[1000] = {0};

void mul_int(int *a, int m) {
    long long carry = 0;
    for (int i = 0; a[i] || carry; i++) {
        carry += (long long)a[i] * m;
        a[i] = carry % BASE;
        carry /= BASE;
    }
}

void add_int(int *sum, int *a) {
    int carry = 0;
    for (int i = 0; a[i] || sum[i] || carry; i++) {
        carry += sum[i] + a[i];
        sum[i] = carry % BASE;
        carry /= BASE;
    }
}

void print_big(int *a) {
    int i = 999;
    while (i > 0 && a[i] == 0) i--;
    printf("%d", a[i--]);
    for (; i >= 0; i--) printf("%0*d", WIDTH, a[i]);
    puts("");
}

int main() {
    for (int i = 1; i <= 100; i++) {
        mul_int(a, i);
        add_int(sum, a);
        printf("%d! = ", i); print_big(a);
    }
    printf("Sum = "); print_big(sum);
    return 0;
}

策略三：Python/BC 等高級語言驗證/生成

# Python 一行搞定
print(sum(__import__('math').factorial(i) for i in range(1, 101)))

用於**生成標準答案**、驗證 C 實現正確性、快速原型。

總結

• **首選 long long + %lld** 解決 20! 以內問題（64 位系統 long 也可）。
• **格式字符串必須匹配類型**：long long 用 %lld，uint64_t 用 PRIu64 (inttypes.h)。
• 超出 64 位：**GMP 庫最專業**、手寫大整數最鍛煉、Python 最快驗證。
• 避免 int/long 混用，統一用 int32_t/int64_t (stdint.h) 明確寬度。