×

# New Method For Finding Modular Inverse

 6 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 566●4●12●17 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)

 4 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. answered 26 Jul '14, 18:43 221●3●4 accept rate: 27% Thank you. I was looking for the proof. (29 Jul '14, 14:02)
 toggle preview community wiki:
Preview

By Email:

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:

×1,664
×639
×105

question asked: 14 Jul '14, 13:00

question was seen: 4,852 times

last updated: 29 Jul '14, 14:02