HDU 1066 N! 最後非零數字：大數與遞歸巧解

題目挑戰

求 N! 末尾非零位，N 高達 10¹⁰⁰，需大數處理。直接模擬乘法會 TLE，必須數學化簡。

核心數學推導

1. 剝離因子 2 和 5

末尾 0 由 2×5 產生。將 N! 分解為 2ᵃ·5ᵇ·R，其中 R 不含 2,5。配對 min(a,b) 對 2 和 5 形成 10，剩餘 2^{a-b}·R 的個位即為答案。

2. 奇數乘積的周期性

去掉 2,5 後剩下的奇數乘積個位呈現周期 8：1,3,7,9,1,3,7,9… 利用此周期可 O(1) 計算任意長度奇數乘積模 10。

3. 遞歸公式（關鍵突破）

定義 F(N) 為 N! 末尾非零位。經推導得：

F(N) = F(⌊N/5⌋) * table[N%10] * 6^{⌊N/5⌋} / 2^{⌊N/5⌋ mod 4}  (mod 10)

其中 `table = {1,1,2,6,4,4,4,8,4,6}` 為 0..9! 去除 5 後的末位。更進一步，右側除 F(N/5) 外以 20 為周期，預計算 `mod[20] = {1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2}`，則：

F(N) = F(N/5) * mod[N%20] (mod 10)

遞歸深度 O(log₅ N)，大數除 5 用高精度除法（乘 2 除 10）模擬。

AC 代碼精華

int mod[20] = {1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2};
char n[1000]; int a[1000];
while (scanf("%s", n) != EOF) {
    int t = 1, len = strlen(n);
    for (int i=0; i=0; --i) {
            c = c*10 + a[i];
            a[i] = c/5; c %= 5;
        }
    }
    printf("%d\n", t);
}

複雜度

每次除 5 掃描 O(L)，L 為位數，遞歸 O(log₅ N) 次，總時間 O(L log N)，極快。

總結

本題展示了如何將看似巨大的大數運算，通過數學規律（周期性、遞歸）轉化為極簡計算，是數論與高精度結合的經典教材。