math_mod/inv.hpp

• View this file on GitHub
• Last update: 2025-01-05 04:43:56+09:00
• Include: #include "math_mod/inv.hpp"

Required by

• convolution/convolution_arb.hpp
• convolution/convolution_int.hpp
• fps/fps_arb.hpp
• math_mod/garner.hpp

Verified with

• verify/yosupo_convolution/convolution_arbitrary.test.cpp
• verify/yosupo_fps/fps_exp_arb.test.cpp
• verify/yosupo_fps/fps_inv_arb.test.cpp
• verify/yosupo_fps/fps_log_arb.test.cpp

Code

#ifndef KK2_MATH_MOD_INV_HPP
#define KK2_MATH_MOD_INV_HPP 1

#include <algorithm>

namespace kk2 {

// require: modulo >= 1
template <class T> constexpr T mod_inversion(T a, T modulo) {
    a %= modulo;
    if (a < 0) a += modulo;
    T s = modulo, t = a;
    T m0 = 0, m1 = 1;
    while (t) {
        T u = s / t;
        std::swap(s -= t * u, t);
        std::swap(m0 -= m1 * u, m1);
    }
    if (m0 < 0) m0 += modulo;
    return m0;
}

} // namespace kk2

#endif // KK2_MATH_MOD_INV_HPP

#line 1 "math_mod/inv.hpp"



#include <algorithm>

namespace kk2 {

// require: modulo >= 1
template <class T> constexpr T mod_inversion(T a, T modulo) {
    a %= modulo;
    if (a < 0) a += modulo;
    T s = modulo, t = a;
    T m0 = 0, m1 = 1;
    while (t) {
        T u = s / t;
        std::swap(s -= t * u, t);
        std::swap(m0 -= m1 * u, m1);
    }
    if (m0 < 0) m0 += modulo;
    return m0;
}

} // namespace kk2

Back to top page