Mod/mod_inv.hpp

• View this file on GitHub
• Last update: 2024-06-05 18:50:12+07:00
• Include: #include "Mod/mod_inv.hpp"

Required by

• Mod/Primitive_root.hpp
• Modint/Barrett_2.hpp
• NT/prime/factorize.hpp

Verified with

• test/yosupo/Math/factorize_yosupo.test.cpp
• test/yosupo/Math/primitive_root.test.cpp
• test/yosupo/Sample/fast_modinv.test.cpp

Code

#pragma once

#include <cassert>
#include <type_traits>

// gcd(a, m) != 1 return -1 
template <typename T>
T inv_mod(T a, T m) {
  if (m == 1) return 0;
  if (a >= m) a %= m;
  if (a < 0) a += m;
  if(__gcd(a,m)!=1) return -1;
  T b = m, s = 1, t = 0;
  while (true) {
    if (a == 1) return s;
    t -= b / a * s;
    b %= a;
    if (b == 1) return t + m;
    s -= a / b * t;
    a %= b;
  }
}

#line 2 "Mod/mod_inv.hpp"

#include <cassert>
#include <type_traits>

// gcd(a, m) != 1 return -1 
template <typename T>
T inv_mod(T a, T m) {
  if (m == 1) return 0;
  if (a >= m) a %= m;
  if (a < 0) a += m;
  if(__gcd(a,m)!=1) return -1;
  T b = m, s = 1, t = 0;
  while (true) {
    if (a == 1) return s;
    t -= b / a * s;
    b %= a;
    if (b == 1) return t + m;
    s -= a / b * t;
    a %= b;
  }
}

Back to top page