c++ - 两个二项式系数模 10^9 + 7 的 GCD

Question

有给出0 ≤ k ≤ n ≤ 500000, 0 ≤ l ≤ m ≤ 500000。

我需要共同计算GCD(C(n, k), C(m, l))模 10^9 + 7。

我的尝试：

我想到了fourmula的技巧： C(n, k) = n*(n-1)*...*(n-k+1) / k!

例如，假设 l >= k： GCD( C(n, k), C(m, l) ) = = GCD( n*(n-1)*...*(n-k+1) / k!, m*(m-1)*...*(m-l+1) / l! ) = = GCD( n*(n-1)*...*(n-k+1)*(k + 1)*...*l/ l!, m*(m-1)*...*(m-l+1) / l! ) = = GCD( n*(n-1)*...*(n-k+1)*(k + 1)*...*l, m*(m-1)*...*(m-l+1) ) / l!

用二进制取幂求逆l!到 10^9 + 5 很好，但我不知道如何继续。

这(k + 1)*...*l部分毁了一切。n*(n-1)*...*(n-k+1)如果和的乘数之间存在交集，我会发现一些好处 m*(m-1)*...*(m-l+1)，但如果没有，则整个 GCD 必须包含在这(k + 1)*...*l部分中。

下一步是什么？对剩余乘数使用原生 GCD 算法？又太长了，因为需要计算它们的乘积，所以上面的操作看起来毫无意义。

我走对了吗？有什么技巧可以解决这个问题吗？

标签： c++algorithmmathnumber-theorybinomial-coefficients

Answer 1

在juvian的建议下，这很简单。我怎么没有想到分解的想法！

我的 C++ 代码如下：

#include <iostream>
#include <algorithm>

#define NMAX 500000
#define MOD 1000000007

using namespace std;


long long factorial(long long n)
{
    long long ans = 1;
    for (int i = 2; i <= n; i++)
        ans = ans * i % MOD;
    return ans;
}

long long binPow(long long num, int p)
{
    if (p == 0)
        return 1;

    if (p % 2 == 1)
        return binPow(num, p - 1) * num % MOD;
    if (p % 2 == 0)
    {
        long long b = binPow(num, p / 2);
        return b * b % MOD;
    }
}

void primesFactorize(long long n, long long primes[])
{
    for (int d = 2; d * d <= n; d++)
        while(n % d == 0)
        {
            n /= d;
            primes[d]++;
        }
    if (n > 1) primes[n]++;
}

long long primes1[NMAX];
long long primes2[NMAX];

int main()
{
    long long n, k, m, l;

    cin >> k >> n >> l >> m;

    if (k > l)
    {
        swap(n, m);
        swap(k, l);
    }

    for (int i = n - k + 1; i <= n; i++)
        primesFactorize(i, primes1);

    for (int i = k + 1; i <= l; i++)
        primesFactorize(i, primes1);

    for (int i = m - l + 1; i <= m; i++)
        primesFactorize(i, primes2);

    for (int i = 2; i <= max(n, m); i++)
        primes1[i] = min(primes1[i], primes2[i]);

    long long ans = 1;
    for (int i = 2; i <= max(n, m); i++)
        for (int j = 1; j <= primes1[i]; j++)
            ans = ans * i % MOD;

    ans = ans * binPow(factorial(l), MOD - 2) % MOD;

    cout << ans << endl;
    return 0;
}