Mod Inv
(math/mod_inv.hpp)

• View this file on GitHub
• Last update: 2023-10-26 11:41:06+09:00
• Include: #include "math/mod_inv.hpp"

説明

素数 $p$ に対して、 $x^{-1} \pmod p$ を返す。線形で逆元テーブルを作成する。

Depends on

• modint/base.hpp

Required by

• $f(x)$ の逆関数 ( $O(N\log^2{N})$ ) (fps/compositional_inverse_of_fps.hpp)
• Formal Power Series (Sparse) (fps/fps_sparse.hpp)
• $\sqrt{f}$ (fps/fps_sqrt.hpp)
• $\prod (1 - x^{a_i}) \mod x^d$ (fps/product_of_one_minus_xn.hpp)
• $\prod (1 + x^{a_i}) \mod x^d$ (fps/product_of_one_plus_xn.hpp)

Verified with

• test/aoj/aoj_3361.test.cpp
• test/math/Partition_Function_FPS.test.cpp
• test/math/Sharp_P_Subset_Sum.test.cpp
• test/polynomial/Compositional_Inverse_of_Formal_Power_Series_Large.test.cpp
• test/polynomial/Exp_of_Formal_Power_Series_Sparse.test.cpp
• test/polynomial/Inv_of_Formal_Power_Series_Sparse.test.cpp
• test/polynomial/Log_of_Formal_Power_Series_Sparse.test.cpp
• test/polynomial/Pow_of_Formal_Power_Series_Sparse.test.cpp
• test/polynomial/Sqrt_of_Formal_Power_Series.test.cpp
• test/polynomial/Sqrt_of_Formal_Power_Series_Sparse.test.cpp

Code

#pragma once

#include <cassert>
#include <vector>

#include "../modint/base.hpp"

namespace ebi {

template <Modint mint> mint inv(int n) {
    static const int mod = mint::mod();
    static std::vector<mint> dat = {0, 1};
    assert(0 <= n);
    if (n >= mod) n -= mod;
    while (int(dat.size()) <= n) {
        int num = dat.size();
        int q = (mod + num - 1) / num;
        dat.emplace_back(dat[num * q - mod] * mint(q));
    }
    return dat[n];
}

}  // namespace ebi

#line 2 "math/mod_inv.hpp"

#include <cassert>
#include <vector>

#line 2 "modint/base.hpp"

#include <concepts>
#include <iostream>
#include <utility>

namespace ebi {

template <class T>
concept Modint = requires(T a, T b) {
    a + b;
    a - b;
    a * b;
    a / b;
    a.inv();
    a.val();
    a.pow(std::declval<long long>());
    T::mod();
};

template <Modint mint> std::istream &operator>>(std::istream &os, mint &a) {
    long long x;
    os >> x;
    a = x;
    return os;
}

template <Modint mint>
std::ostream &operator<<(std::ostream &os, const mint &a) {
    return os << a.val();
}

}  // namespace ebi
#line 7 "math/mod_inv.hpp"

namespace ebi {

template <Modint mint> mint inv(int n) {
    static const int mod = mint::mod();
    static std::vector<mint> dat = {0, 1};
    assert(0 <= n);
    if (n >= mod) n -= mod;
    while (int(dat.size()) <= n) {
        int num = dat.size();
        int q = (mod + num - 1) / num;
        dat.emplace_back(dat[num * q - mod] * mint(q));
    }
    return dat[n];
}

}  // namespace ebi

Back to top page