演算法逐步推導（二）：階乘尾部零計數 — 從暴力模擬到對數時間數學解法

複雜度：O(n²) 時間、O(n) 空間。僅適合極小 n 驗證邏輯。

方法二：數學公式法 (標準解，O(log n))

核心洞見：階乘中因子 2 的個數遠多於 5，**尾部零個數 = 因子 5 的總個數**。

每 5 個數貢獻 1 個 5，每 25 個數額外貢獻 1 個 (25=5²)，每 125 個再額外 1 個...

公式：

zeros(n) = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ... = Σ ⌊n/5ᵏ⌋

O(log₅ n) 程式碼

long long trailingZeros(long long n) {
    long long count = 0;
    for (long long p = 5; p <= n; p *= 5) {
        count += n / p;
        if (p > n / 5) break;  // 防止 p*=5 溢位
    }
    return count;
}

驗證範例

延伸：任意進制尾部零

若求 n! 在 base B 下尾部零：

1. 分解 B = p₁ᵉ¹ × p₂ᵉ² × ... (質因數分解)。
2. 對每個質因數 pᵢ，計算 n! 中 pᵢ 的指數 expᵢ = Σ ⌊n/pᵢᵏ⌋。
3. 答案 = min(⌊expᵢ / eᵢ⌋)。

複雜度比較

核心思維：不要模擬過程，要分析本質。尾部零本質是質因數 2 與 5 的配對，而 2 過剩，故只需數 5。這種「質因數分解視角」是解決大數組合數學問題的萬能鑰匙。