階乘質因數分解：Legendre 公式計算質因子個數

階乘質因數分解：Legendre 公式計算質因子個數

給定素數 m 和整數 n (0 ≤ n ≤ 10000)，求 n! 的質因數分解中素數 m 出現的次數。這是數論中的經典問題，直接應用Legendre 公式。

Legendre 公式

n! 中素數 p 的指數為：

eₚ(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ... (直到 pᵏ > n)

原理解析

• ⌊n/p⌋：1 到 n 中 p 的倍數個數（每個貢獻至少 1 個 p）
• ⌊n/p²⌋：p² 的倍數個數（額外貢獻第 2 個 p）
• ⌊n/p³⌋：p³ 的倍數個數（額外貢獻第 3 個 p）
• 以此類推...

樣例驗證

n=100, m=5：

⌊100/5⌋ + ⌊100/25⌋ + ⌊100/125⌋ = 20 + 4 + 0 = 24

n=16, m=2：

⌊16/2⌋ + ⌊16/4⌋ + ⌊16/8⌋ + ⌊16/16⌋ = 8 + 4 + 2 + 1 = 15

高效實現

#include <cstdio>

int count_factor_in_factorial(int n, int p) {
    int count = 0;
    for (long long pk = p; pk <= n; pk *= p) {
        count += n / pk;
        if (pk > n / p) break; // 防止 pk *= p 溢出
    }
    return count;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d %d", &n, &m);
        printf("%d\n", count_factor_in_factorial(n, m));
    }
    return 0;
}

複雜度分析

• 循環次數：O(logₚ n)
• 對於 n=10000, p=2：log₂10000 ≈ 14 次循環
• 測試組數 s ≤ 100，總操作數極小，瞬間通過

常見錯誤與優化

1. 溢出保護：使用 long long 存儲 pk，並在乘法前檢查 `pk > n / p`
2. 輸入順序：題目給的是 n, m，注意讀入順序
3. 邊界情況：n=0 時 0! = 1，無質因子，結果為 0

擴展應用

• 求 n! 末尾有多少個 0：min(count(2), count(5)) = count(5)
• 組合數 C(n,k) 的質因數分解：eₚ(C(n,k)) = eₚ(n!) - eₚ(k!) - eₚ((n-k)!)
• 卡特蘭數、階乘相關組合問題的質因數分析

Legendre 公式是處理階乘質因數問題的核心工具，掌握它能輕鬆解決大量組合數論問題。