ГКД двух биномиальных коэффициентов по модулю 10 ^ 9 + 7
Там даны 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),
но если нет, то весь ГКД должен содержаться в этом (k + 1)*...*l часть.
А потом что? Использование собственного алгоритма GCD для оставшихся множителей?
Слишком долго опять из-за необходимости рассчитывать их произведение, так что манипуляции выше кажутся бессмысленными.
Я на правильном пути?
Есть ли какая-то хитрость, чтобы придумать эту проблему?
Решение
С советом Ювиана это очень просто. Как я не придумал идею факторизации!
Мой код 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;
}
Другие решения
Других решений пока нет …
detector