We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Yes, you're totally right, thanks for your observation. I guess the author was so hell-bent on using Euler's formula that he probably computed every modular inverse by raising to p - 2 power mindlessly and totally forgot that it only holds when gcd(a, p) = 1. I used EEA instead. After seeing your post I added assertion against non-invertible numbers as on Wiki page and it became obvious what was going on.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Expressions V2
You are viewing a single comment's thread. Return to all comments →
Yes, you're totally right, thanks for your observation. I guess the author was so hell-bent on using Euler's formula that he probably computed every modular inverse by raising to
p - 2
power mindlessly and totally forgot that it only holds whengcd(a, p) = 1
. I used EEA instead. After seeing your post I added assertion against non-invertible numbers as on Wiki page and it became obvious what was going on.