Is calculating MMI of 2**n through pow(pow(2,n),M2,M) and pow(pow(2,n),M1,M) is same,when do we use M1 and when do we use M2,given that 2 and M are coprime. See this question https://www.hackerrank.com/challenges/numberofsubsets Here is lalit kundu's solution.Why p1 instead of p2? https://www.hackerrank.com/rest/contests/infinitum10/challenges/numberofsubsets/hackers/xorfire/download_solution asked 28 Jul '15, 15:49

Hi sandeep, no doubt for calculating MMI we use M2 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 https://en.wikipedia.org/wiki/Fermat%27s_little_theorem so according to theorem (2 power m = 2 power g : where g = m %(M1)) that's why M1 is used in the code and after that we use M2 also because both thing are different M2 is due to MMI. and M1 is due to Fermats theorem (a power p1)%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%(71) =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 :) answered 30 Jul '15, 00:28
