Mixing
GCD of two binomial coefficients modulo 10^9 + 7
Clash Royale CLAN TAG#URR8PPP GCD of two binomial coefficients modulo 10^9 + 7
There are given 0 ≤ k ≤ n ≤ 500000, 0 ≤ l ≤ m ≤ 500000.
0 ≤ k ≤ n ≤ 500000
0 ≤ l ≤ m ≤ 500000
I need co calculate GCD(C(n, k), C(m, l)) modulo 10^9 + 7.
GCD(C(n, k), C(m, l))
My attempt:
I thought about tricks with fourmula:C(n, k) = n*(n-1)*...*(n-k+1) / k!
C(n, k) = n*(n-1)*...*(n-k+1) / k!
For example, suppose 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!
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!
Inversing l! with binary exponentiation to 10^9 + 5 is fine, but I don't know how to continue.
l!
This (k + 1)*...*l part ruins everything. I can find some benefit if there is intersection between multipliers of n*(n-1)*...*(n-k+1) and m*(m-1)*...*(m-l+1),
but if not, whole GCD must be contained in this (k + 1)*...*l part.
(k + 1)*...*l
n*(n-1)*...*(n-k+1)
m*(m-1)*...*(m-l+1)
(k + 1)*...*l
And what's next? Using native GCD algorithm for remaining multipliers?
Too long again because of need to calculate product of them, so that manipulations above look meaningless.
Am I on a right way?
Is there some trick to come up with this problem?
Thank you! How didn't I manage to do this! About the link: it is from some local contest, so that there is no access to it, unfortunately.
– Pavel
1 hour ago
1 Answer
1
With juvian`s advice it is very simple. How didn't I come up with an idea of factorization!
My C++ code below:
#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;
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
What is the link to the original problem? As for the remaining multipliers, there is no need to calculate the product, you could get the prime factorization of it in O(n sqrt n), then do the same for the other product and get the gcd between both without doing the explicit product. After you get that, you can do the product while keeping the modulo
– juvian
11 hours ago