math/mod-inv.hpp

• View this file on GitHub
• Last update: 2023-07-08 14:12:19+09:00
• Include: #include "math/mod-inv.hpp"

Depends on

• math/base.hpp
• math/extgcd.hpp

Required by

• string/rolling-hash.hpp

Verified with

• test/aoj/alds1/14_B.test.cpp

Code

#pragma once

#include "./base.hpp"
#include "./extgcd.hpp"

namespace matumoto {
  constexpr ll modinv(ll n, ll mod) {
    ll x = 0, y = 0;
    extgcd(n, mod, x, y);
    return (x % mod + mod) % mod;
  }
} // namespace matumoto

#line 2 "math/mod-inv.hpp"

#line 2 "math/base.hpp"

namespace matumoto {
  using namespace std;
  using ll = long long;
} // namespace matumoto
#line 2 "math/extgcd.hpp"

#line 4 "math/extgcd.hpp"

namespace matumoto {
  constexpr ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
      x = 1;
      y = 0;
      return a;
    }
    ll d = extgcd(b, a % b, y, x);
    y = y - (a / b) * x;
    return d;
  }
} // namespace matumoto
#line 5 "math/mod-inv.hpp"

namespace matumoto {
  constexpr ll modinv(ll n, ll mod) {
    ll x = 0, y = 0;
    extgcd(n, mod, x, y);
    return (x % mod + mod) % mod;
  }
} // namespace matumoto

Back to top page