階乘尾部零的個數：1000! 末尾有多少個 0？數學與算法完整解析

問題描述

求 1000! (1000 階乘) 的十進制表示末尾連續有多少個 0？

1000! = 1 × 2 × 3 × ... × 999 × 1000

核心數學原理

十進制下，末尾的 `0` 來源於因子 10 = 2 × 5。在階乘分解中，質因數 2 的個數**遠多於** 5 的個數 (每隔 2 個數有一個 2，每隔 5 個數才有一個 5)。因此，**尾部 0 的個數完全取決於質因數 5 的個數**。

計算公式 (勒让德公式)

對於任意正整數 n，n! 中質因數 p 的指數為：

count_p(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ... (直到商為 0)

對於尾部 0，p = 5：

zeros(n!) = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ⌊n/625⌋ + ...

1000! 手算演示

答案：1000! 末尾有 249 個 0。

通用 Java 實現 (O(log₅ n) 時間複雜度)

public class FactorialTrailingZeros {

    /**
     * 計算 n! 末尾 0 的個數
     * 時間複雜度：O(log₅ n)，空間複雜度：O(1)
     */
    public static long trailingZeros(long n) {
        if (n < 0) throw new IllegalArgumentException("階乘僅定義於非負整數");
        long count = 0;
        for (long divisor = 5; divisor <= n; divisor *= 5) {
            count += n / divisor;
            // 防止 divisor * 5 溢出 long 最大值 (雖然 n 通常不會那麼大)
            if (divisor > Long.MAX_VALUE / 5) break;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println("1000! 尾部 0 的個數: " + trailingZeros(1000)); // 249
        System.out.println("100! 尾部 0 的個數: " + trailingZeros(100));   // 24
        System.out.println("10! 尾部 0 的個數: " + trailingZeros(10));     // 2
        System.out.println("0! 尾部 0 的個數: " + trailingZeros(0));       // 0
    }
}

為什麼原文的「遍歷 1..1000 除以 2 和 5」雖然能得正確答案，但不是最佳解？

• 時間複雜度：原文 O(n log n) (需遍歷每個數並反覆除) vs 公式法 O(log n)。
• 擴展性：原文無法處理 10^9! 等大數；公式法瞬間計算。
• 本質理解：原文掩蓋了「2 足夠多，5 是瓶頸」的核心數學洞察。

延伸應用：二進制下尾部 0 的個數

同理，二進制下尾部 0 取決於質因數 2 的個數：

public static long trailingZerosBinary(long n) {
    long count = 0;
    for (long d = 2; d <= n; d *= 2) count += n / d;
    return count;
}
// 等價於 n - Long.bitCount(n) (n 的二進制中 1 的個數)

總結

階乘尾部零問題是經典的數論應用。**核心洞察：尾部 0 由因子 10 決定，10 = 2×5，2 充足，數 5 即可。** 掌握勒让德公式，可在 O(log n) 時間解決任意大小 n 的問題，這是算法面試、競賽編程與數學建模的必備技能。