138. Modular Inverse
MediumExtended EuclidFermat
Print x with 0 ≤ x < m and a·x ≡ 1 (mod m), or -1 if no inverse exists.
Input format
A single line: a m
Output format
The inverse, or -1.
Example 1
Input
3 11
Output
4
Example 2
Input
10 17
Output
12
Constraints
1 ≤ a, m ≤ 10⁹
Read input from standard input and print the answer to standard output. Your code is judged against 5 test cases, most of them hidden.
Loading the MyLoginn IDE…