Is calculating MMI of 2**n through pow(pow(2,n),M-2,M) and pow(pow(2,n),M-1,M) is same,when do we use M-1 and when do we use M-2,given that 2 and M are co-prime.
See this question
Here is lalit kundu’s solution.Why p-1 instead of p-2?
https://www.hackerrank.com/rest/contests/infinitum10/challenges/number-of-subsets/hackers/xorfire/download_solution
Hi sandeep,
no doubt for calculating MMI we use M-2 because it is case of (2 power n) but what happen when power of 2 is much large like (2 power m : where m = 2 power n) so in this case we apply Fermat’s little theorem Fermat's little theorem - Wikipedia
so according to theorem (2 power m = 2 power g : where g = m %(M-1)) that’s why M-1 is used in the code and after that we use M-2 also because both thing are different
M-2 is due to MMI. and M-1 is due to Fermats theorem
(a power p-1)%p=1
lets take simple example of Fermats theorem you have to calculate (2 power 9)%7 then first method is to call power function which calculate power in logarithmic time but second method is to apply Fermat’s theorem means first find 9%(7-1) =3 and now call power function to calculate (2 power 3)%7 answer will be same in both case means first you have to reduce that power and then calculate power of number both of these operation require logarithmic power function. i think it would help you but please open wikipedia for more info and limitation of theorem 