逆元 (inverse element)
(include/emthrm/math/mod_inv.hpp)

• View this file on GitHub
• Last update: 2023-02-23 21:59:12+09:00
• Include: #include "emthrm/math/mod_inv.hpp"

$ax \equiv 1 \pmod{m}$ を満たす $x = a^{-1}$ である。

• $a^{-1}$ が存在するとき $a \cdot a^{-1} + my = 1$ を満たす $y \in \mathbb{Z}$ が存在する。拡張 Euclid の互除法を用い、時間計算量 $O(\log{M})$ で $(a^{-1}, y)$ を求められる。
• Fermat の小定理より、$m \in \mathbb{P}$ かつ $a \perp m$ を満たすとき $a^{-1} \equiv a^{m - 2} \pmod{m}$ が成り立つ。時間計算量 $O(\log{M})$ で求められる。
• オイラーの定理より、$a \perp m$ を満たすとき $a^{-1} \equiv a^{\varphi(m) - 1} \pmod{m}$ が成り立つ。時間計算量 $O(\sqrt{M})$ で求められる。

時間計算量

$O(\log{M})$

仕様

名前	戻り値
long long mod_inv(long long a, const int m);	$a$ の逆元。ただし存在しないときは $-1$ を返す。

参考文献

• https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a
• https://github.com/kirika-comp/articles/blob/c16612f266202ec6ce0f462601dd4db110add534/pre-seisuuron.pdf

Required by

• 中国剰余定理 (Chinese remainder theorem) (include/emthrm/math/chinese_remainder_theorem.hpp)
• 連立線形合同式 (simultaneous linear congruence) (include/emthrm/math/simultaneous_linear_congruence.hpp)

Verified with

• 数学/中国剰余定理 (test/math/chinese_remainder_theorem.test.cpp)
• 数学/連立線形合同式 (test/math/simultaneous_linear_congruence.test.cpp)

Code

#ifndef EMTHRM_MATH_MOD_INV_HPP_
#define EMTHRM_MATH_MOD_INV_HPP_

#include <numeric>
#include <utility>

namespace emthrm {

long long mod_inv(long long a, const int m) {
  if ((a %= m) < 0) a += m;
  if (std::gcd(a, m) != 1) return -1;
  long long x = 1;
  for (long long b = m, u = 0; b > 0;) {
    const long long q = a / b;
    std::swap(a -= q * b, b);
    std::swap(x -= q * u, u);
  }
  x %= m;
  return x < 0 ? x + m : x;
}

}  // namespace emthrm

#endif  // EMTHRM_MATH_MOD_INV_HPP_

#line 1 "include/emthrm/math/mod_inv.hpp"



#include <numeric>
#include <utility>

namespace emthrm {

long long mod_inv(long long a, const int m) {
  if ((a %= m) < 0) a += m;
  if (std::gcd(a, m) != 1) return -1;
  long long x = 1;
  for (long long b = m, u = 0; b > 0;) {
    const long long q = a / b;
    std::swap(a -= q * b, b);
    std::swap(x -= q * u, u);
  }
  x %= m;
  return x < 0 ? x + m : x;
}

}  // namespace emthrm

Back to top page