modint/montgomery-modint.hpp
- View this file on GitHub
- Last update: 2023-05-29 20:50:32+09:00
- Include:
#include "modint/montgomery-modint.hpp"
Required by
fps/arbitrary-fps.hpp
Multipoint Evaluation(高速化版) (fps/fast-multieval.hpp)
三角関数 (fps/fps-circular.hpp)
関数の合成( $\mathrm{O}(N^2)$ ) (fps/fps-composition-fast-old.hpp)
fps/online-fps.hpp
math/bigint-all.hpp
math/bigint-binary.hpp
Garner's algorithm for bigint (math/bigint-garner.hpp)
math/bigint-gcd.hpp
math/bigint-rational.hpp
math/bigint-to-hex.hpp
多倍長整数 (math/bigint.hpp)
modulo/strassen.hpp
ntt/arbitrary-ntt.hpp
Chirp Z-transform(Bluestein's algorithm) (ntt/chirp-z.hpp)
Cooley-Tukey FFT Algorithm (ntt/cooley-tukey-ntt.hpp)
多変数巡回畳み込み (ntt/multivariate-circular-convolution.hpp)
Rader's FFT Algorithm (ntt/rader-ntt.hpp)
Wildcard Pattern Matching (string/wildcard-pattern-matching.hpp)
頂点間の距離の度数分布 (tree/frequency-table-of-tree-distance.hpp)
Verified with
verify/verify-aoj-ntl/aoj-ntl-2-a.test.cpp
verify/verify-aoj-ntl/aoj-ntl-2-b.test.cpp
verify/verify-aoj-ntl/aoj-ntl-2-c.test.cpp
verify/verify-aoj-ntl/aoj-ntl-2-d.test.cpp
verify/verify-aoj-ntl/aoj-ntl-2-e.test.cpp
verify/verify-aoj-ntl/aoj-ntl-2-f.test.cpp
verify/verify-aoj-other/aoj-2171-bigrational.test.cpp
verify/verify-unit-test/arbitrary-ntt-mod18446744069414584321.test.cpp
verify/verify-unit-test/bigint-gcd.test.cpp
verify/verify-unit-test/bigint.test.cpp
verify/verify-unit-test/bigint2.test.cpp
verify/verify-unit-test/bigint3.test.cpp
verify/verify-unit-test/bigrational.test.cpp
verify/verify-unit-test/binomial-table.test.cpp
verify/verify-unit-test/composite-exp.test.cpp
verify/verify-unit-test/composition.test.cpp
verify/verify-unit-test/debug.test.cpp
verify/verify-unit-test/dual-fps.test.cpp
verify/verify-unit-test/fast-inv-o1.test.cpp
verify/verify-unit-test/fast-inv.test.cpp
verify/verify-unit-test/fft2d.test.cpp
verify/verify-unit-test/fps-sparse.test.cpp
verify/verify-unit-test/fps.test.cpp
verify/verify-unit-test/garner-bigint.test.cpp
verify/verify-unit-test/gauss-elimination.test.cpp
verify/verify-unit-test/inverse-matrix.test.cpp
verify/verify-unit-test/karatsuba.test.cpp
verify/verify-unit-test/mf.test.cpp
verify/verify-unit-test/modint.test.cpp
verify/verify-unit-test/multieval.test.cpp
verify/verify-unit-test/multiplicative-function.test.cpp
verify/verify-unit-test/multipoint-binomial-sum.test.cpp
verify/verify-unit-test/p-recursive.test.cpp
verify/verify-unit-test/partial-fraction-decomposition.test.cpp
verify/verify-unit-test/polynomial-matrix-prod.test.cpp
verify/verify-unit-test/rational-number.test.cpp
verify/verify-unit-test/rbst-segment-tree.test.cpp
verify/verify-unit-test/relaxed-convolution.test.cpp
verify/verify-unit-test/rerooting.test.cpp
verify/verify-unit-test/set-function.test.cpp
verify/verify-unit-test/stirling-matrix.test.cpp
verify/verify-unit-test/strassen.test.cpp
verify/verify-unit-test/sum-of-mf.test.cpp
verify/verify-unit-test/template.test.cpp
verify/verify-yosupo-ds/yosupo-deque-operate-all-composite.test.cpp
verify/verify-yosupo-ds/yosupo-dynamic-sequence-range-affine-range-sum-splay.test.cpp
verify/verify-yosupo-ds/yosupo-dynamic-sequence-range-affine-range-sum-treap.test.cpp
verify/verify-yosupo-ds/yosupo-dynamic-sequence-range-affine-range-sum.test.cpp
verify/verify-yosupo-ds/yosupo-dynamic-tree-vertex-add-path-sum.test.cpp
verify/verify-yosupo-ds/yosupo-dynamic-tree-vertex-set-path-composite.test.cpp
verify/verify-yosupo-ds/yosupo-lazysegtree-2.test.cpp
verify/verify-yosupo-ds/yosupo-lazysegtree.test.cpp
verify/verify-yosupo-ds/yosupo-point-set-range-composite-dynamic-segtree.test.cpp
verify/verify-yosupo-ds/yosupo-point-set-range-composite-rbstseg.test.cpp
verify/verify-yosupo-ds/yosupo-point-set-range-composite-rbstseg2.test.cpp
verify/verify-yosupo-ds/yosupo-range-add-range-sum-linkcuttree.test.cpp
verify/verify-yosupo-ds/yosupo-range-affine-point-get-2.test.cpp
verify/verify-yosupo-ds/yosupo-range-affine-point-get.test.cpp
verify/verify-yosupo-ds/yosupo-range-affine-range-sum-dynamic-segtree.test.cpp
verify/verify-yosupo-ds/yosupo-range-affine-range-sum-rbstseg.test.cpp
verify/verify-yosupo-ds/yosupo-range-affine-sqdec.test.cpp
verify/verify-yosupo-ds/yosupo-range-parallel-unionfind.test.cpp
verify/verify-yosupo-ds/yosupo-range-set-range-composite.test.cpp
verify/verify-yosupo-ds/yosupo-static-rectangle-add-rectangle-sum.test.cpp
verify/verify-yosupo-ds/yosupo-swag.test.cpp
verify/verify-yosupo-ds/yosupo-vertex-set-path-composite.test.cpp
verify/verify-yosupo-fps/yosupo-composition-fast.test.cpp
verify/verify-yosupo-fps/yosupo-composition-large.test.cpp
verify/verify-yosupo-fps/yosupo-composition.test.cpp
verify/verify-yosupo-fps/yosupo-compositional-inverse-large.test.cpp
verify/verify-yosupo-fps/yosupo-compositional-inverse-newton.test.cpp
verify/verify-yosupo-fps/yosupo-compositional-inverse.test.cpp
verify/verify-yosupo-fps/yosupo-division-of-polynomials.test.cpp
verify/verify-yosupo-fps/yosupo-exp-arb.test.cpp
verify/verify-yosupo-fps/yosupo-exp-newton-method-2.test.cpp
verify/verify-yosupo-fps/yosupo-exp-newton-method.test.cpp
verify/verify-yosupo-fps/yosupo-exp-ofps.test.cpp
verify/verify-yosupo-fps/yosupo-exp-relaxed-convolution.test.cpp
verify/verify-yosupo-fps/yosupo-exp.test.cpp
verify/verify-yosupo-fps/yosupo-factorial-p-recursive.test.cpp
verify/verify-yosupo-fps/yosupo-factorial.test.cpp
verify/verify-yosupo-fps/yosupo-interpolation.test.cpp
verify/verify-yosupo-fps/yosupo-inv-arb.test.cpp
verify/verify-yosupo-fps/yosupo-inv-newton-method.test.cpp
verify/verify-yosupo-fps/yosupo-inv-of-polynomials.test.cpp
verify/verify-yosupo-fps/yosupo-inv-ofps.test.cpp
verify/verify-yosupo-fps/yosupo-inv-relaxed-convolution.test.cpp
verify/verify-yosupo-fps/yosupo-inv.test.cpp
verify/verify-yosupo-fps/yosupo-linear-recurrence.test.cpp
verify/verify-yosupo-fps/yosupo-log-arb.test.cpp
verify/verify-yosupo-fps/yosupo-log.test.cpp
verify/verify-yosupo-fps/yosupo-multieval-fast.test.cpp
verify/verify-yosupo-fps/yosupo-multieval.test.cpp
verify/verify-yosupo-fps/yosupo-polynomial-interpolation-fast.test.cpp
verify/verify-yosupo-fps/yosupo-polynomial-root-finding.test.cpp
verify/verify-yosupo-fps/yosupo-pow-arb.test.cpp
verify/verify-yosupo-fps/yosupo-pow.test.cpp
verify/verify-yosupo-fps/yosupo-product-of-polynomial-sequence.test.cpp
verify/verify-yosupo-fps/yosupo-sample-point-shift.test.cpp
verify/verify-yosupo-fps/yosupo-sparse-exp.test.cpp
verify/verify-yosupo-fps/yosupo-sparse-inv.test.cpp
verify/verify-yosupo-fps/yosupo-sparse-log.test.cpp
verify/verify-yosupo-fps/yosupo-sparse-pow.test.cpp
verify/verify-yosupo-fps/yosupo-sqrt.test.cpp
verify/verify-yosupo-fps/yosupo-stirling-1st-row.test.cpp
verify/verify-yosupo-fps/yosupo-stirling-1st.test.cpp
verify/verify-yosupo-fps/yosupo-stirling-2nd-row.test.cpp
verify/verify-yosupo-fps/yosupo-stirling-2nd.test.cpp
verify/verify-yosupo-fps/yosupo-sum-of-exp-poly-limit.test.cpp
verify/verify-yosupo-fps/yosupo-sum-of-exp-poly.test.cpp
verify/verify-yosupo-fps/yosupo-taylor-shift.test.cpp
verify/verify-yosupo-graph/yosupo-exp-of-set-power-series.test.cpp
verify/verify-yosupo-graph/yosupo-frequency-table-of-tree-distance.test.cpp
verify/verify-yosupo-graph/yosupo-point-set-tree-path-composite-sum-fixed-root-2.test.cpp
verify/verify-yosupo-graph/yosupo-point-set-tree-path-composite-sum-fixed-root.test.cpp
verify/verify-yosupo-graph/yosupo-point-set-tree-path-composite-sum.test.cpp
verify/verify-yosupo-graph/yosupo-tree-path-composite-sum.test.cpp
verify/verify-yosupo-math/yosupo-addition-of-big-integers.test.cpp
verify/verify-yosupo-math/yosupo-addition-of-hex.test.cpp
verify/verify-yosupo-math/yosupo-characteristic-polynomial.test.cpp
verify/verify-yosupo-math/yosupo-determinant-matrixlib.test.cpp
verify/verify-yosupo-math/yosupo-determinant-of-matrix-bbla.test.cpp
verify/verify-yosupo-math/yosupo-determinant-of-sparse-matrix-bbla.test.cpp
verify/verify-yosupo-math/yosupo-determinant.test.cpp
verify/verify-yosupo-math/yosupo-division-of-big-integers.test.cpp
verify/verify-yosupo-math/yosupo-division-of-hex.test.cpp
verify/verify-yosupo-math/yosupo-gcd-convolution.test.cpp
verify/verify-yosupo-math/yosupo-hafnian-of-matrix.test.cpp
verify/verify-yosupo-math/yosupo-inverse-matrix.test.cpp
verify/verify-yosupo-math/yosupo-lcm-convolution.test.cpp
verify/verify-yosupo-math/yosupo-linear-equation-2.test.cpp
verify/verify-yosupo-math/yosupo-linear-equation.test.cpp
verify/verify-yosupo-math/yosupo-matrix-product-strassen.test.cpp
verify/verify-yosupo-math/yosupo-matrix-product-vectorize-modint.test.cpp
verify/verify-yosupo-math/yosupo-multiplication-of-big-integers.test.cpp
verify/verify-yosupo-math/yosupo-multiplication-of-hex.test.cpp
verify/verify-yosupo-math/yosupo-polynomial-composite-set-power-series.test.cpp
verify/verify-yosupo-math/yosupo-pow-of-matrix-2.test.cpp
verify/verify-yosupo-math/yosupo-pow-of-matrix.test.cpp
verify/verify-yosupo-math/yosupo-rank-of-matrix.test.cpp
verify/verify-yosupo-math/yosupo-sparse-determinant.test.cpp
verify/verify-yosupo-math/yosupo-subset-convolution-fast.test.cpp
verify/verify-yosupo-math/yosupo-subset-convolution.test.cpp
verify/verify-yosupo-math/yosupo-sum-of-totient-2.test.cpp
verify/verify-yosupo-math/yosupo-sum-of-totient-3.test.cpp
verify/verify-yosupo-math/yosupo-sum-of-totient.test.cpp
verify/verify-yosupo-ntt/yosupo-convolution-arbitrarylengthntt.test.cpp
verify/verify-yosupo-ntt/yosupo-convolution-arbitraryntt-arbitrarymodint.test.cpp
verify/verify-yosupo-ntt/yosupo-convolution-arbitraryntt-arbitraryprimemodint.test.cpp
verify/verify-yosupo-ntt/yosupo-convolution-arbitraryntt.test.cpp
verify/verify-yosupo-ntt/yosupo-convolution-chirp-z.test.cpp
verify/verify-yosupo-ntt/yosupo-convolution-large.test.cpp
verify/verify-yosupo-ntt/yosupo-convolution-ntt-avx2.test.cpp
verify/verify-yosupo-ntt/yosupo-convolution-ntt-sse42.test.cpp
verify/verify-yosupo-ntt/yosupo-convolution-ntt.test.cpp
verify/verify-yosupo-ntt/yosupo-convolution-on-z-pz.test.cpp
verify/verify-yosupo-ntt/yosupo-convolution-relaxed-convolution.test.cpp
verify/verify-yosupo-ntt/yosupo-convolution-schoenhage-radix2.test.cpp
verify/verify-yosupo-ntt/yosupo-inliner-multiply.test.cpp
verify/verify-yosupo-ntt/yosupo-multiplicative-convolution.test.cpp
verify/verify-yosupo-ntt/yosupo-multipoint-evaluation-chirp-z.test.cpp
verify/verify-yosupo-ntt/yosupo-multivariate-circular-convolution.test.cpp
verify/verify-yosupo-other/yosupo-a-plus-b-128bit-bigint.test.cpp
verify/verify-yosupo-string/yosupo-number-of-subsequences.test.cpp
verify/verify-yosupo-string/yosupo-wildcard-pattern-matching.test.cpp
verify/verify-yuki/yuki-0117.test.cpp
verify/verify-yuki/yuki-0125.test.cpp
verify/verify-yuki/yuki-0214.test.cpp
verify/verify-yuki/yuki-0215-nth-term.test.cpp
verify/verify-yuki/yuki-0215.test.cpp
verify/verify-yuki/yuki-0303.test.cpp
verify/verify-yuki/yuki-0502.test.cpp
verify/verify-yuki/yuki-0720.test.cpp
verify/verify-yuki/yuki-0886.test.cpp
verify/verify-yuki/yuki-0890.test.cpp
verify/verify-yuki/yuki-0896.test.cpp
verify/verify-yuki/yuki-0963-circular.test.cpp
verify/verify-yuki/yuki-0963.test.cpp
verify/verify-yuki/yuki-1080.test.cpp
verify/verify-yuki/yuki-1112-sparse.test.cpp
verify/verify-yuki/yuki-1112.test.cpp
verify/verify-yuki/yuki-1145-frac.test.cpp
verify/verify-yuki/yuki-1145.test.cpp
verify/verify-yuki/yuki-1269.test.cpp
verify/verify-yuki/yuki-1303.test.cpp
verify/verify-yuki/yuki-1504.test.cpp
verify/verify-yuki/yuki-1510.test.cpp
verify/verify-yuki/yuki-1533.test.cpp
verify/verify-yuki/yuki-1781.test.cpp
verify/verify-yuki/yuki-1783.test.cpp
verify/verify-yuki/yuki-1875.test.cpp
verify/verify-yuki/yuki-1939-2.test.cpp
verify/verify-yuki/yuki-1939-sparse-pow.test.cpp
verify/verify-yuki/yuki-1939.test.cpp
verify/verify-yuki/yuki-2231.test.cpp
verify/verify-yuki/yuki-2360.test.cpp
verify/verify-yuki/yuki-2580.test.cpp
verify/verify-yuki/yuki-2588.test.cpp
verify/verify-yuki/yuki-2661.test.cpp
verify/verify-yuki/yuki-2883.test.cpp
Code
#pragma once
template <uint32_t mod>
struct LazyMontgomeryModInt {
using mint = LazyMontgomeryModInt;
using i32 = int32_t;
using u32 = uint32_t;
using u64 = uint64_t;
static constexpr u32 get_r() {
u32 ret = mod;
for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret;
return ret;
}
static constexpr u32 r = get_r();
static constexpr u32 n2 = -u64(mod) % mod;
static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");
static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");
static_assert(r * mod == 1, "this code has bugs.");
u32 a;
constexpr LazyMontgomeryModInt() : a(0) {}
constexpr LazyMontgomeryModInt(const int64_t &b)
: a(reduce(u64(b % mod + mod) * n2)){};
static constexpr u32 reduce(const u64 &b) {
return (b + u64(u32(b) * u32(-r)) * mod) >> 32;
}
constexpr mint &operator+=(const mint &b) {
if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;
return *this;
}
constexpr mint &operator-=(const mint &b) {
if (i32(a -= b.a) < 0) a += 2 * mod;
return *this;
}
constexpr mint &operator*=(const mint &b) {
a = reduce(u64(a) * b.a);
return *this;
}
constexpr mint &operator/=(const mint &b) {
*this *= b.inverse();
return *this;
}
constexpr mint operator+(const mint &b) const { return mint(*this) += b; }
constexpr mint operator-(const mint &b) const { return mint(*this) -= b; }
constexpr mint operator*(const mint &b) const { return mint(*this) *= b; }
constexpr mint operator/(const mint &b) const { return mint(*this) /= b; }
constexpr bool operator==(const mint &b) const {
return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
}
constexpr bool operator!=(const mint &b) const {
return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
}
constexpr mint operator-() const { return mint() - mint(*this); }
constexpr mint operator+() const { return mint(*this); }
constexpr mint pow(u64 n) const {
mint ret(1), mul(*this);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
constexpr mint inverse() const {
int x = get(), y = mod, u = 1, v = 0, t = 0, tmp = 0;
while (y > 0) {
t = x / y;
x -= t * y, u -= t * v;
tmp = x, x = y, y = tmp;
tmp = u, u = v, v = tmp;
}
return mint{u};
}
friend ostream &operator<<(ostream &os, const mint &b) {
return os << b.get();
}
friend istream &operator>>(istream &is, mint &b) {
int64_t t;
is >> t;
b = LazyMontgomeryModInt<mod>(t);
return (is);
}
constexpr u32 get() const {
u32 ret = reduce(a);
return ret >= mod ? ret - mod : ret;
}
static constexpr u32 get_mod() { return mod; }
};
#line 2 "modint/montgomery-modint.hpp"
template <uint32_t mod>
struct LazyMontgomeryModInt {
using mint = LazyMontgomeryModInt;
using i32 = int32_t;
using u32 = uint32_t;
using u64 = uint64_t;
static constexpr u32 get_r() {
u32 ret = mod;
for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret;
return ret;
}
static constexpr u32 r = get_r();
static constexpr u32 n2 = -u64(mod) % mod;
static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");
static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");
static_assert(r * mod == 1, "this code has bugs.");
u32 a;
constexpr LazyMontgomeryModInt() : a(0) {}
constexpr LazyMontgomeryModInt(const int64_t &b)
: a(reduce(u64(b % mod + mod) * n2)){};
static constexpr u32 reduce(const u64 &b) {
return (b + u64(u32(b) * u32(-r)) * mod) >> 32;
}
constexpr mint &operator+=(const mint &b) {
if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;
return *this;
}
constexpr mint &operator-=(const mint &b) {
if (i32(a -= b.a) < 0) a += 2 * mod;
return *this;
}
constexpr mint &operator*=(const mint &b) {
a = reduce(u64(a) * b.a);
return *this;
}
constexpr mint &operator/=(const mint &b) {
*this *= b.inverse();
return *this;
}
constexpr mint operator+(const mint &b) const { return mint(*this) += b; }
constexpr mint operator-(const mint &b) const { return mint(*this) -= b; }
constexpr mint operator*(const mint &b) const { return mint(*this) *= b; }
constexpr mint operator/(const mint &b) const { return mint(*this) /= b; }
constexpr bool operator==(const mint &b) const {
return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
}
constexpr bool operator!=(const mint &b) const {
return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
}
constexpr mint operator-() const { return mint() - mint(*this); }
constexpr mint operator+() const { return mint(*this); }
constexpr mint pow(u64 n) const {
mint ret(1), mul(*this);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
constexpr mint inverse() const {
int x = get(), y = mod, u = 1, v = 0, t = 0, tmp = 0;
while (y > 0) {
t = x / y;
x -= t * y, u -= t * v;
tmp = x, x = y, y = tmp;
tmp = u, u = v, v = tmp;
}
return mint{u};
}
friend ostream &operator<<(ostream &os, const mint &b) {
return os << b.get();
}
friend istream &operator>>(istream &is, mint &b) {
int64_t t;
is >> t;
b = LazyMontgomeryModInt<mod>(t);
return (is);
}
constexpr u32 get() const {
u32 ret = reduce(a);
return ret >= mod ? ret - mod : ret;
}
static constexpr u32 get_mod() { return mod; }
};