HDU 5407 CRB and Candies：二項式係數 LCM 的數論規律

題目大意

計算 f(n) = LCM( C(n,0), C(n,1), ..., C(n,n) ) mod 1e9+7，n ≤ 1e6，多測試用例。

關鍵結論

f(n) = LCM(1, 2, ..., n+1) / (n+1)

證明略（利用質因子指數比較）。

預處理 LCM 前綴

• 篩出所有質數 ≤ 1e6+1。
• 對每個質數 p，其所有冪次 p, p², p³, ... 在對應位置標記需乘 p。
• 前綴乘積 g[i] = LCM(1..i)：
   g[1]=1; for i=2..N: g[i] = g[i-1] * lcmFactor[i] % MOD，其中 lcmFactor[i] 為質數冪貢獻（若 i 是質數冪則為該質數，否則 1）。

模逆元計算

答案 = g[n+1] * inv(n+1) % MOD，用快速冪求逆元。

完整代碼

#include 
using namespace std;
const int MOD = 1e9+7;
const int MAXN = 1000005;
vector primes;
int lcmFactor[MAXN];
long long g[MAXN];

int modPow(long long a, long long e) {
    long long r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

void init() {
    vector isPrime(MAXN, true);
    for (int i = 2; i * i < MAXN; ++i)
        if (isPrime[i])
            for (int j = i*i; j < MAXN; j += i) isPrime[j] = false;
    for (int i = 2; i < MAXN; ++i) if (isPrime[i]) primes.push_back(i);
    fill(lcmFactor, lcmFactor+MAXN, 1);
    for (int p : primes) {
        for (long long pk = p; pk < MAXN; pk *= p)
            lcmFactor[pk] = p;
    }
    g[1] = 1;
    for (int i = 2; i < MAXN; ++i)
        g[i] = g[i-1] * lcmFactor[i] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        ++n;
        long long ans = g[n] * modPow(n, MOD-2) % MOD;
        cout << ans << "\n";
    }
    return 0;
}

複雜度

• 篩質數 + 標記冪次：O(N log log N)。
• 前綴乘積：O(N)。
• 查詢：O(log MOD) 快速冪。
• 總體預處理 ~1e6，查詢極快。