This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#include "math/mod_inv.hpp"
素数 $p$ に対して、 $x^{-1} \pmod p$ を返す。線形で逆元テーブルを作成する。
#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