How to calculate C(n, r) modulo m, m is of the form p^a, where p is prime.

Here C(n, r) means n choose r. The range of n and r is large (of the order of 10^18) so it cannot be solved by calculating the power of primes. Also m is less than 10^6. I tried reading the generalization of Lucas Theorem, but could not understand it. It will be really helpful if someone could explain a feasible method to solve the problem.

Till now I have tried this. I stored every prime number from 1 to n in an array p[]. Then calculated the power of pi 1<=i<=|p| in n! and added it to arr[i]. Similarly calculated the power of pi 1 <=i<=|p| from 1 to r in r! and subtracted it from arr[i]. Same for (n-r)!. Then multiplied (p[i]^arr[i])%(p^a) to answer while taking modulo. But this runs in O(n) which is too slow for the above mentioned constraints.

There is a citation in the wikipedia page of Lucas's theorem for generalized form of Lucas's theorem but the link is not working.


If this is you trying to solve a problem in a programming competition, don't read any further, because using outside help is cheating.

Very simple. You are calculating a product of numbers x(i) modulo m. These numbers x (i) are consecutive integers. If there are n or more of them, then one must be equal to 0 (modulo m). And in that case, the whole product is 0 (modulo m). Actually, if there are a*p or more, then you have a numbers divisible by p, so the product is divisible by m = p^a, so the product is 0.

Therefore, all the cases where the product is not 0 modulo m can be solved with fewer than m multiplications.

  • Yes. But what if the numerator and denominator have the same power of p. In this case they cancel out and the result is not zero. eg. C(50, 10) modulo (25) = 20, C(6, 2) modulo (2) = 1. – abc xyz May 17 '17 at 7:20
  • Don't think of C(n,r) in terms of a fraction. The denominator always entirely cancels with part of the numerator. The easiest way of thinking of it is as specifying part of the sequence of products that is omitted. – Jules May 17 '17 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.