Mod inverse
(Mylib/Number/Mod/mod_inv.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• mod_inv(a, m)
  • $ax = 1 \pmod m$を満たすxを求める。
  • $gcd(a, m) = 1$を満たさなければならない。
  • Time complexity $O(\log N)$

Requirements

Notes

Problems

References

Required by

• Binomial coefficient (Mylib/Combinatorics/binomial_coefficient.cpp)
• Mod logarithm (Mylib/Number/Mod/mod_log.cpp)
• Garner algorithm (Mylib/Number/garner.cpp)
• Linear congruence equation (Mylib/Number/linear_congruence_equation.cpp)

Verified with

• test/yosupo-judge/binomial_coefficient/main.test.cpp
• test/yosupo-judge/discrete_logarithm_mod/main.test.cpp

Code

#pragma once
#include <cstdint>
#include <utility>

namespace haar_lib {
  constexpr int64_t mod_inv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;

    while (b) {
      int64_t t = a / b;
      a -= t * b;
      a = a ^ b;
      b = a ^ b;
      a = a ^ b;

      u -= t * v;
      u = u ^ v;
      v = u ^ v;
      u = u ^ v;
    }

    u %= m;
    if (u < 0) u += m;

    return u;
  }
}  // namespace haar_lib

#line 2 "Mylib/Number/Mod/mod_inv.cpp"
#include <cstdint>
#include <utility>

namespace haar_lib {
  constexpr int64_t mod_inv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;

    while (b) {
      int64_t t = a / b;
      a -= t * b;
      a = a ^ b;
      b = a ^ b;
      a = a ^ b;

      u -= t * v;
      u = u ^ v;
      v = u ^ v;
      u = u ^ v;
    }

    u %= m;
    if (u < 0) u += m;

    return u;
  }
}  // namespace haar_lib

Back to top page