You are viewing a single comment's thread. Return to all comments →
In the editorial, I am unable to understant the part where inverse of n is being calculated.
Precisely, this part =>
for i in xrange(2,p): inv[i] = (p - p/i) * inv[p%i] % p
I know how to calculate inverse using extended Euler's theorem. It would be nice if you could elaborate the logic behind it or share some link.
p%i = p - (p/i) * i (by definition of modulo. Note that all division are integer division)
p%i * inv[i] = p - (p/i) * i * inv[i] = p - (p/i)
inv[i] = inv[p%i] * p - (p/i)
Seems like cookies are disabled on this browser, please enable them to open this website
I agree to HackerRank's Terms of Service and Privacy Policy.
Ajob Subsequence
You are viewing a single comment's thread. Return to all comments →
In the editorial, I am unable to understant the part where inverse of n is being calculated.
Precisely, this part =>
calculate inverses mod p
for i in xrange(2,p): inv[i] = (p - p/i) * inv[p%i] % p
I know how to calculate inverse using extended Euler's theorem. It would be nice if you could elaborate the logic behind it or share some link.
p%i = p - (p/i) * i (by definition of modulo. Note that all division are integer division)
p%i * inv[i] = p - (p/i) * i * inv[i] = p - (p/i)
inv[i] = inv[p%i] * p - (p/i)