I have tried solving this question http://www.codechef.com/IOPC2013/problems/IOPC13H , but iam not able to figure out an algorithm, can any one explain/ideas about??
We know the formula for binomial coefficients: C(n,k)=n!/k!(n-k)!. We’re asked to compute LCM(C(n,k)) over all 0 <= k <= n, but since the numerator of the fraction is constant and just the denominator (which is its divisor) changes, it’s sufficient to compute D = GCD(k!(n-k)!) over all k, and the answer will be n!/D (since D is coprime to the prime modulus, division modulo 10^9+7 is done using the modular inverse, so it’s n!*D^(10^9+5)).
We can see that D(n) (D for n) divides D(n+1): D(n) divides all k!(n-k)!, and it can’t be divided by anything if we just multiply all k!(n-k)! by n+1-k (and adding k=n+1, which is the same as k=0 and thus can be ignored). The problem now reduces to finding the quotient of D(n)/D(n-1) for all n.
For this type of problems, there’s one excellent strategy: write a bruteforce, find out answers for n <= 50 and try to guess the general formula. If you do this, you find out that the quotient is 1 for all prime n+1 and n+1 for almost all non-prime n+1. The only exceptions are prime powers - for n+1=p^a, the quotient D(n)/D(n-1) is p^(a-1).
This gives us an easy way to compute D for all n <= 10^5 - for every n, we just need to check if it’s prime or prime power, and that can be done by O(sqrt(n)) prime decomposition. Then, we compute (in O(log 10^9+5)) the modular inverse, update the current n! (multiply it by n+1, mod 10^9+7) and get the answers for all n in O(n sqrt(n)) total time. Every test case can be answered instantly, so the total time complexity is O(t+n sqrt(n)).
1 Like