LeetCode 172. 階乘尾部零計數：對數時間數學解法詳解

LeetCode 172. 階乘尾部零計數：對數時間數學解法詳解

給定整數 n，求 n! 末尾連續 0 的個數。本文揭示尾部 0 來源於因子 2×5，因 2 遠多於 5，問題轉化為統計 n! 中因子 5 的個數，給出 O(log₅ n) 時間、O(1) 空間的極簡數學解法。

核心數學洞察

尾部 0 由 10 產生，10 = 2 × 5。在 n! 的質因數分解中，因子 2 的個數遠大於因子 5（每隔 2 個數有一個 2，每隔 5 個數才有一個 5）。因此，**尾部 0 的個數 = n! 中因子 5 的總個數**。

因子 5 計數公式

每 5 個數貢獻至少一個 5（5, 10, 15...），每 25 個數額外貢獻一個 5（25=5²），每 125 個數再額外貢獻一個 5（125=5³）……

count = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ... 直到商為 0

C 語言實現（迭代版）

int trailingZeroes(int n) {
    int count = 0;
    while (n > 0) {
        n /= 5;
        count += n;
    }
    return count;
}

遞歸版（同樣 O(log n) 空間）

int trailingZeroes(int n) {
    if (n == 0) return 0;
    return n/5 + trailingZeroes(n/5);
}

邊界與測試

為什麼不用計算 n! 直接數 0？

• n! 增長極快：13! 超過 32 位 int，21! 超過 64 位 long long。
• 大數運算需高精度庫，極慢且過度設計。
• 數學公式直接給出答案，O(log n) 時間，無溢出風險。

擴展：任意進制下尾部 0

若求 n! 在 b 進制下尾部 0 個數：分解 b = p₁^e₁ * p₂^e₂ ...，對每個質因子 pᵢ 計算 n! 中 pᵢ 的指數 cntᵢ，答案為 min(cntᵢ / eᵢ)。

總結

階乘尾部零計數是「質因數分解思想」在算法題中的經典應用。將「計算巨大數值」轉化為「統計質因子指數」，以 O(log n) 時間解決看似需要大數運算的問題，體現了數學建模在算法優化中的核心價值。