大數階乘計算：高精度乘法演算法與C語言實作

問題描述

計算 n! (n ≤ 5000) 並輸出完整結果。5000! 約有 16326 位十進制數字，遠超 unsigned long long (20 位) 範圍，需實作**高精度乘法**（大數乘法）。

核心演算法：模擬手工列竖式乘法

• 以 **基數 10000** (10⁴) 為單位，每個陣列元素存 4 位十進制數字
• 5000! 需約 16326/4 ≈ 4082 個元素，宣告 int a[10000] 足夠
• 從 1 乘到 n，每輪處理進位

完整 C 代碼（優化版）

#include <stdio.h>
#include <math.h>

int main() {
    int n;
    while(scanf("%d", &n) == 1) {
        if(n < 0 || n > 5000) continue;

        int a[10000] = {0};
        a[0] = 1;
        int len = 0;  // 當前最高有效位索引

        for(int i = 2; i <= n; i++) {
            int carry = 0;
            for(int j = 0; j <= len; j++) {
                long long prod = (long long)a[j] * i + carry;
                a[j] = prod % 10000;
                carry = prod / 10000;
            }
            while(carry > 0) {
                a[++len] = carry % 10000;
                carry /= 10000;
            }
        }

        // 輸出：最高位不補零，其餘補齊 4 位
        printf("%d", a[len]);
        for(int i = len - 1; i >= 0; i--)
            printf("%04d", a[i]);
        printf("\n");
    }
    return 0;
}

關鍵優化點

位數估算公式

利用對數性質：

log10(n!) = log10(1) + log10(2) + ... + log10(n)
位數 = floor(log10(n!)) + 1

或使用斯特靈公式近似：

log10(n!) ≈ n*log10(n/e) + 0.5*log10(2πn)

複雜度分析

• 時間：O(n × M) ，M 為平均位數 ≈ O(n log n)
• 空間：O(M) = O(n log n)
• 5000! 約 0.1 秒內完成（現代 CPU）

進階優化方向

• 更大基數：10⁹ (32位) 或 10¹⁸ (64位)，減少陣列長度
• FFT 乘法：O(n log n log log n)，適合極大數 (n > 10⁵)
• 質因子分解法：n! = ∏ p^e，先篩質數再快速冪
• 二進制分割：分治相乘，減少大數乘小數操作

測試驗證

輸入: 50
輸出: 30414093201713378043612608166064768844377641568960512000000000000

與樣例輸出完全一致 ✓

總結

大數階乘是高精度運算的經典入門題。掌握「基數分解 + 進位傳播 + 位數追蹤」三大核心技巧，可擴展至大數加減乘除、冪模、組合數等廣泛應用。