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

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 算法？由于需要计算它们的乘积，又太长了，所以上面的操作看起来毫无意义。

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

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;
}

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

GCD of two binomial coefficients modulo 10^9 + 7

c++

algorithm

math

binomial-coefficients

number-theory