### Samsam's blog

By Samsam, 7 years ago,

I always see problems that need to print the result of C(n,m) mod a prime number where C(n,m) = n!/(m!*(n-m)!) the factorial formula of binomial coefficients. I've searched for it and I found that I need to find the multiplicative inverse using extended Euclidean algorithm and I've learnt it. I hope if somebody could tell me the fastest way to find C(n,m) mod P (P is a prime) using extended Euclidean algorithm and I would be thankful if there was a code. Thanks a lot.

• 0

 » 7 years ago, # | ← Rev. 2 →   0 I don't know how to " find C(n,m) mod P (P is a prime) using extended Euclidean algorithm". But, this is the way i use to find C(n,m) mod P : - If n is small (~10^4), you can caculate C(n,m) mod p with a simple O(n^2) dynamic programming. - With bigger n, you can see problem Super Sum on this lịnk. Author used Fermat Little Theorem to calculate inverse modulo p of denominator in C(n,m). Hope it's useful.
•  » » 7 years ago, # ^ |   +3 There is also a solution with extended Euclidean algorithm. You can find more about it on e-maxx (Russian). But it looks like solution with Euler's Theorem is easier. We know that So, Or for prime m
 » 7 years ago, # |   0 Try this.
•  » » 7 years ago, # ^ |   0 Thanks it too useful
•  » » 3 weeks ago, # ^ |   0 thanks
 » 7 years ago, # |   +1 if is a prime, then .so u can use (say) in above formula, and
•  » » 7 years ago, # ^ |   0 thanks it is clear now
•  » » 4 weeks ago, # ^ |   0 It's all about the Fermat's little theorem.. Efficient time complexity would be O(k*log(p)) which is much better