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?? asked 28 Feb '14, 20:15

We know the formula for binomial coefficients: C(n,k)=n!/k!(nk)!. 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!(nk)!) 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!(nk)!, and it can't be divided by anything if we just multiply all k!(nk)! by n+1k (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(n1) 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 nonprime n+1. The only exceptions are prime powers  for n+1=p^a, the quotient D(n)/D(n1) is p^(a1). 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)). answered 01 Mar '14, 00:25
