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

×

A doubtregarding MMI(modulo multiplacative inverse)

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

sandeep9's gravatar image

3★sandeep9
4782827
accept rate: 4%


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 :)

link

answered 30 Jul '15, 00:28

admin123's gravatar image

5★admin123
1.2k12
accept rate: 28%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

Related questions