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

求組合數 C(n, k) 的約數個數。n ≤ 500，直接計算組合數會溢出，需利用質因子分解性質：C(n, k) = n! / (k! * (n-k)!)。先篩出 500 以內質數，預處理每個階乘的質因子指數，再相減得到組合數的質因子分解，約數個數為各指數+1 的乘積。

算法步驟

1. 線性篩法求 500 內質數。
2. 預處理 divide[i][p]：i! 中質數 p 的指數（i/p + i/p^2 + ...）。
3. 預處理 ans[n][k]：C(n, k) 的約數個數 = ∏(divide[n][p] - divide[k][p] - divide[n-k][p] + 1)。
4. 查詢 O(1) 輸出。

核心代碼

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

bool vis[502];
int prime[102], cnt;
int divide[502][102];
long long ans[502][502];

void init() {
    memset(vis, 0, sizeof(vis));
    cnt = 0;
    for (int i = 2; i < 500; ++i) {
        if (!vis[i]) prime[cnt++] = i;
        for (int j = 0; j < cnt && i * prime[j] < 500; ++j) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
    for (int i = 0; i < cnt; ++i)
        for (int j = 2; j < 500; ++j)
            divide[j][i] = j / prime[i] + divide[j / prime[i]][i];

    for (int i = 2; i < 500; ++i) {
        for (int j = 1; j < i; ++j) {
            ans[i][j] = 1;
            for (int k = 0; k < cnt && divide[i][k]; ++k) {
                int e = divide[i][k] - divide[j][k] - divide[i-j][k];
                if (e) ans[i][j] *= (e + 1);
            }
        }
    }
}

int main() {
    init();
    int n, k;
    while (cin >> n >> k) {
        if (k == 0 || n == k) { puts("1"); continue; }
        if (k > n - k) k = n - k; // 對稱性優化
        cout << ans[n][k] << endl;
    }
    return 0;
}

複雜度

• 預處理：O(500 * 質數個數) ≈ 500 * 95，極快。
• 查詢：O(1)。
• 空間：ans[500][500] 約 2MB。