If we have a * x = 1 (mod kMod), we call x is a multiplicative inverse of a when modular is kMod (in this post, kMod is a prime number). Usually we use a^-1 to represent it. Binary Exponentiation Given a and kMod, we can get a^-1 in O(logkMod) time. Dynamic Programming This solves…
Modular Multiplicative Inverse
Posted on