Hi, I learned about modular multiplicative inverse with modulo M (M is a prime number) using: (a^(M-2) ) MOD M
Now I would like to learn how calculate modular multiplicative inverse with modulo no prime.
Could someone give me one or two examples how to calculate it? For example COMB(8,3) = 8! /(3! * (8-3)!) = 56 , then COMB(8,3) MOD 6 = 2.
Thanks in advance. (Sorry for my poor english)
You can use DP to calculate C(n , r) ( C(n , r) = (C(n — 1 , r — 1) + C(n — 1 , r))% MOD ) in O(n * r) instead of using factorial.
You are right... I didn't think about it... Thanks
CF community knows about this task. It's better to ask for help in two days.
I'll wait for the answer... I solved this problem http://codeforces.com/problemset/problem/300/C and I would know how solve it with no prime number. The problem in Codechef is very interesting too.. Thanks for the link...
Someone can to answer me? I'd like to know how solve it.
http://lmgtfy.com/?q=modular+multiplicative+inverse&l=1
Read wiki about extended gcd to calculate modulo reverse. Sometimes if gcd(x, y) is not equal to 1 you can use following trick. Let's M = p1^s1 * p2^s2 * ... * pk^sk, x = p1^x1 * ... * pk^xk * A, y = p1^y1 * ... * pk^yk * B. Then x / y = p1^(x1-y1) * ... * pk^(xk-yk) * ((A * B) % M). You can use this trick to calculate COMB(i, j) through factorials because final powers are non negative.
In fact, in this problem, you want to solve this question:
"Find t, that (x*t) mod M = y"
However when M is not prime, t may be not unique. In your example, M=6, y=8*7*6=0 (mod M), x=3*2*1=0 (mod M), certainly we have no way to find which number t is.
That means, multiply in mod-non-prime group can lead to losing of information and the lost information can not be recovery. If you change M in a problem to a non-prime, the problem may become not solvable.
Have you try Euler Theorem ?