階乘尾部去零取後九位算法：C/Java 實現與邊界處理

問題描述

輸入整數 n（最大 10,000,000），計算 n!，去掉末尾的 0，再取最後 9 位作為一個整數輸出（前導 0 省略）。例如 n=38 輸出 742912。

核心思路

1. 階乘過程中不斷乘以 i，每步立即除去因子 10（即 while (r % 10 == 0) r /= 10;），防止尾部 0 累積導致溢出。
2. 只保留最後 9 位有效數字（r %= 1000000000），避免大數運算。
3. 最終結果直接輸出，前導 0 會被自然省略。

參考代碼 (C)

int foo(int n) {
    long r = 1;
    for (int i = 2; i <= n; i++) {
        r *= i;
        while (r % 10 == 0) r /= 10;  // 去除尾部 0
        r %= 1000000000;              // 只保留後 9 位
    }
    return (int)r;
}

int main() {
    printf("%d\n", foo(38));  // 輸出 742912
    return 0;
}

關鍵點說明

• 使用 long（或 64 位整數）足以容納中間結果（10^9 * 10^7 仍在 64 位範圍）。
• 對於 Java，可用 long 並同理處理；n 極大時同樣適用，因為每步都取模。
• 注意：n=0 或 1 時結果為 1，邏輯自動覆蓋。