math/mod_inv.cpp

• View this file on GitHub
• Last update: 2021-11-10 20:31:05+09:00

Depends on

• math/inv_gcd.cpp
• math/rem_euclid.cpp

Required by

• algorithm/convolution_arbitrary_mod.cpp
• algorithm/convolution_int.cpp
• math/dynamic_modint.cpp

Verified with

• test/convolution_arbitrary_mod.test.cpp

Code

#pragma once
#include <cassert>
#include "inv_gcd.cpp"

template <class T> constexpr T mod_inv(const T& a, const T& mod) {
    const auto [g, x] = inv_gcd(a, mod);
    assert(g == 1);
    return x;
}

#line 2 "math/mod_inv.cpp"
#include <cassert>
#line 2 "math/inv_gcd.cpp"
#include <type_traits>
#include <utility>
#line 3 "math/rem_euclid.cpp"

template <class T> constexpr T rem_euclid(T value, const T& mod) {
    assert(mod > 0);
    return (value %= mod) >= 0 ? value : value + mod;
}
#line 5 "math/inv_gcd.cpp"

template <class T> constexpr std::pair<T, T> inv_gcd(const T& a, const T& b) {
    using U = std::make_signed_t<T>;
    U t = rem_euclid(a, b);
    if (t == 0) return {b, 0};
    U s = b, m0 = 0, m1 = 1;
    while (t != 0) {
        const U u = s / t;
        s -= t * u;
        m0 -= m1 * u;
        U tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    if (m0 < 0) m0 += b / s;
    return {(T)s, (T)m0};
}
#line 4 "math/mod_inv.cpp"

template <class T> constexpr T mod_inv(const T& a, const T& mod) {
    const auto [g, x] = inv_gcd(a, mod);
    assert(g == 1);
    return x;
}

Back to top page