大整數階乘計算：遞推法與數組模擬實現

問題背景

計算 n! (n < 100) 所有有效數字。100! 約 158 位，遠超 64 位整數範圍 (20! 已溢出)，需數組模擬大整數存儲與運算。

數組存儲設計

• a[0]：當前有效位數長度
• a[1]：個位
• a[2]：十位
• a[i]：第 i-1 位 (10^i-1 位)

即低位在低索引，高位在高索引，符合人工乘法習慣，便於進位處理。

遞推算法核心：利用 (k-1)! 累加 k-1 次得 k!

已知 4! = 24，求 5!：24 + 24 + 24 + 24 = 96？錯！正確是 24 × 5 = 120。
但乘法可轉化為累加：k! = (k-1)! × k = (k-1)! + (k-1)! + ... + (k-1)! (共 k 次)。
更高效：k! = (k-1)! × k 直接逐位乘法 + 進位。本文採用累加法演示遞推思想。

完整 C 代碼實現

#include <stdio.h>
#include <stdlib.h>

#define MAXN 1000  // 足夠存儲 100! (158 位)

// 將 a 更新為 a * k (通過累加 k-1 次實現)
void pnext(int a[], int k) {
    int *b = (int*)malloc(sizeof(int) * (a[0] + 1));
    int m = a[0];
    
    // 備份原值
    for (int i = 1; i <= m; ++i) b[i] = a[i];
    
    // 累加 k-1 次
    for (int j = 1; j < k; ++j) {
        int carry = 0;
        for (int i = 1; i <= m; ++i) {
            int r = a[i] + b[i] + carry;
            a[i] = r % 10;
            carry = r / 10;
        }
        if (carry) a[++m] = carry; // 處理最高位進位
    }
    free(b);
    a[0] = m;
}

// 輸出大整數
void write(int a[], int k) {
    printf("%4d! = ", k);
    for (int i = a[0]; i >= 1; --i) printf("%d", a[i]);
    printf("\n\n");
}

int main() {
    int a[MAXN] = {0}, n;
    printf("Enter n (n < 100): ");
    scanf("%d", &n);
    
    a[0] = 1; a[1] = 1;  // 1! = 1
    write(a, 1);
    
    for (int k = 2; k <= n; ++k) {
        pnext(a, k);
        write(a, k);
    }
    return 0;
}

算法優化方向

1. 直接乘法替代累加：r = a[i] * k + carry，時間複雜度從 O(k·位數) 降為 O(位數)
2. 基數優化：每個數組元素存 4 位 (基數 10000) 或 9 位 (基數 10⁹，配合 64 位整數)，大幅減少位數與循環次數
3. FFT/NTT 大整數乘法：極大階乘 (如 10000!) 可用快速傅里葉變換實現 O(n log n) 乘法

核心收穫

• 大整數運算本質：數組模擬人工列豎式計算
• 遞推關係：k! = (k-1)! × k，逐步構建
• 進位處理是關鍵：從低位向高位傳播，動態擴展數組長度