Can someone please tell me where my code is failing?? following is the link to my code
http://www.codechef.com/viewsolution/5418119
1 Like
a^(m-1) = 1 mod m was proven only for prime m (Fermat’s little theorem).
For not prime m: a^Fi(m) = 1 (Euler’s theorem), where Fi(x) is Eulers function (Wiki)
1 Like
Line
res=(store[N]*function((store[N-r]*store[r])%M,M-2,M))%M;//inverse modulo
in not correct, since we need to calculate different power in order to find inverse(Fi(m)-1, not m-2). However I’m not sure that the rest is correct.
@syptom the final answer is store[N]/(store[N-r]*store[r]) or it can be written as store[N]*inverse(store[N-r]store[r])
Or (store[N](power((store[N]*store[N-r])%M,M-2,M)))%M
And that is what I am doing. Not getting you; please elaborate!
What I’m trying to say, is that store[N]inverse(store[N-r]store[r]) and (storeN)%M are not always the same number. It’s true only for prime M. When M in not prime, you need to take (store[N](power((store[N]store[N-r])%M, FI(M)-1 ,M)))%M, where FI is Euler’s function for Wikipedia.
For instance 5^6 * 5 is 5 mod 8. 5^3 * 5 = 1 mod 8 (as FI(8) = 4, we have to take 5 ^ (4 - 1)).
When we want to invert a mod m, we need GCD(a,m) to be equal to 1. I don’t know if you ensure that, but when GCD(a,m) is not 1 there is no number b such that ab = 1 mod m.