×

# IOPC13: Crazy Teacher

 0 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 2★sp1rs 963●5●13●27 accept rate: 0%

 1 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)). answered 01 Mar '14, 00:25 7★xellos0 5.9k●5●43●93 accept rate: 10%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,219
×639
×51

question asked: 28 Feb '14, 20:15

question was seen: 2,268 times

last updated: 01 Mar '14, 00:25