## Modular Multiplicative Inverse

View as PDF

Points: 7
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Solve the Modular Multiplicative Inverse problem.

#### Input Specification

Line 1: (, is coprime to )

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 data types, please use a general big integer.

#### Output Specification

Line 1: The modular multiplicative inverse of modulo . The value should be nonnegative.

#### Sample Input

2 7

#### Sample Output

4

• commented on Aug. 17, 2021, 12:26 a.m. edited

Is this problem solvable using Fermat's Little Theorem?

• commented on July 6, 2017, 5: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.

• commented on July 6, 2017, 9:13 p.m.

Try using unsigned long long

• commented on June 13, 2021, 9:15 p.m.

If you're still WAing, try signed 128-bit integers (__int128 in C++).

• commented on Aug. 19, 2016, 2:23 a.m.

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