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

×

New Method For Finding Modular Inverse

I was aware of using a^(mod-2)%mod and extended euclidean for finding modular inverse. But today, while solving CNTWAYS, I came across another method for finding modular inverse. The previous two methods were too slow and apparently this method is much faster.

This is what I found in the Tester's solution:

/* calculate all inverses of 1..8000000 mod MOD */ inv[1] = 1; REP(i,2,800010) inv[i] = MOD - ((MOD/i)*inv[MOD%i]%MOD);

I found it interesting. So anybody has any idea how this code is actually working. Exactly what is this? I have never seen it before.

asked 14 Jul '14, 13:00

forthright's gravatar image

4★forthright
56641217
accept rate: 10%

vai ami o kisu bujlam na. onek time pass korlam but still don't know how it works. @forthright

(14 Jul '14, 14:52) robinmbstu122★

There are three common ways of computing modular inverses. They have all been explained here: http://e-maxx.ru/algo/reverse_element It's a Russian website, so translate it to English, if needed.

link

answered 26 Jul '14, 18:43

aakashc31's gravatar image

4★aakashc31
22134
accept rate: 27%

Thank you. I was looking for the proof.

(29 Jul '14, 14:02) forthright4★
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:

×1,664
×639
×105

question asked: 14 Jul '14, 13:00

question was seen: 4,852 times

last updated: 29 Jul '14, 14:02