You are not logged in. Please login at www.codechef.com to post your questions!

×

# A doubtregarding MMI(modulo multiplacative inverse)

 0 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 https://www.hackerrank.com/challenges/number-of-subsets 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 asked 28 Jul '15, 15:49 3★sandeep9 478●2●8●27 accept rate: 4%

 2 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 https://en.wikipedia.org/wiki/Fermat%27s_little_theorem 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 :) answered 30 Jul '15, 00:28 5★admin123 1.2k●12 accept rate: 28%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×23

question asked: 28 Jul '15, 15:49

question was seen: 554 times

last updated: 30 Jul '15, 00:28