You are not logged in. Please login at to post your questions!


IOPC13: Crazy Teacher

I have tried solving this question , but iam not able to figure out an algorithm, can any one explain/ideas about??

asked 28 Feb '14, 20:15

sp1rs's gravatar image

accept rate: 0%

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

xellos0's gravatar image

accept rate: 10%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 28 Feb '14, 20:15

question was seen: 2,268 times

last updated: 01 Mar '14, 00:25