Modular Multiplicative Inverse

Points: 7

Time limit: 1.0s

Memory limit: 256M

Author:

FatalEagle

Problem type

Problem Description

Solve the Modular Multiplicative Inverse problem.

Input Specification

Line 1: $N, M$ ~N, M~ $(0 \le N < M \le 10^{19}, N$ ~(0 \le N < M \le 10^{19}, N~ is coprime to $M)$ ~M)~

Note: The values will not fit in a 32 bit integer. They will fit in a 64 bit unsigned integer. For languages that do not have unsigned datatypes, please use a general big integer.

Output Specification

Line 1: The modular multiplicative inverse of $N$ ~N~ modulo $M$ ~M~. The value should be nonnegative.

Sample Input

2 7

Sample Output

Comments

0

discoverMe commented on July 8, 2019, 4:27 p.m. ← edit 2 →

how can M be 0? edit: problem was fixed

2

AWB commented on July 6, 2017, 1:02 p.m.

I've implemented a variation of XGCD that does not give a coefficient on M, but am having issues with test case #15 and #22. All the rest are AC. Please help.

5

wleung_bvg commented on July 6, 2017, 5:13 p.m.

Try using unsigned long long

5

Tan commented on Aug. 18, 2016, 10:23 p.m.

Isn't this problem really easy in Java? Java has a built in function for this, which is slow, but still passes.