Modular Multiplicative Inverse

View as PDF
Submit solution
Points: 7
Time limit: 1.0s
Memory limit: 256M
Author:
FatalEagle
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Problem Description

Solve the Modular Multiplicative Inverse problem.

Input Specification

Line 1: N, M (0 \le N < M \le 10^{19}, N is coprime to 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 modulo M. The value should be nonnegative.

Sample Input

2 7

Sample Output

4

Comments


  • 1
    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.