POJ 2992: Divisors - 組合數約數個數計算

問題描述

給定整數 n 和 k（0 ≤ k ≤ n ≤ 431），求組合數 C(n, k) 的不同約數個數。結果保證不超過 2⁶³−1。

數學原理

若正整數 N 的質因子分解為 N = p₁^a₁ × p₂^a₂ × … × p_s^a_s，則其約數個數公式為：

T(N) = (a₁+1)(a₂+1)…(a_s+1)

對於組合數 C(n, k) = n! / (k! × (n−k)!)，其質因子 p 的指數可通過勒讓德公式計算：

e(p) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …

則 C(n, k) 中質因子 p 的指數為 e(n) − e(k) − e(n−k)。

算法步驟

1. 使用埃拉托斯特尼篩法預計算 431 以內的所有質數。
2. 預處理 cnt[i][p] 表示 i! 中質因子 p 的指數（i ≤ 431）。
3. 對每組輸入，遍歷所有 ≤ n 的質數，計算指數差，套用約數個數公式累乘。

核心代碼（C++）

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;

const int MAXN = 431;
int prime[1010], pn = 0;
LL cnt[MAXN+1][MAXN+1];

void sieve() {
    bool vis[MAXN+1] = {0};
    for (int i = 2; i <= MAXN; ++i) {
        if (!vis[i]) prime[pn++] = i;
        for (int j = 0; j < pn && i * prime[j] <= MAXN; ++j) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

void precompute() {
    sieve();
    for (int i = 2; i <= MAXN; ++i) {
        for (int j = 0; j < pn && prime[j] <= i; ++j) {
            int p = prime[j], t = i, sum = 0;
            while (t) { t /= p; sum += t; }
            cnt[i][p] = sum;
        }
    }
}

int main() {
    precompute();
    LL n, k;
    while (scanf("%lld %lld", &n, &k) == 2) {
        LL ans = 1;
        for (int i = 0; i < pn && prime[i] <= n; ++i) {
            int p = prime[i];
            LL e = cnt[n][p] - cnt[k][p] - cnt[n-k][p];
            ans *= (e + 1);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度分析

預處理 O(N log log N + N × π(N))，單次查詢 O(π(n))，完全滿足題目限制。