This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#include "misc/dynamic_modulo.hpp"
#pragma once struct dynamic_modulo { using Fp = dynamic_modulo; using i64 = int64_t; using u64 = uint64_t; using u128 = __uint128_t; static u64 mod; static u64 r; static u64 n2; static u64 get_r() { u64 ret = mod; for (i64 i = 0; i < 5; ++i) ret *= 2 - mod * ret; return ret; } static void set_mod(u64 m) { assert(m < (1LL << 62)); assert((m & 1) == 1); mod = m; n2 = -u128(m) % m; r = get_r(); assert(r * mod == 1); } u64 x; dynamic_modulo() : x(0) {} dynamic_modulo(const int64_t &b) : x(reduce((u128(b) + mod) * n2)){}; static u64 reduce(const u128 &b) { return (b + u128(u64(b) * u64(-r)) * mod) >> 64; } Fp &operator+=(const Fp &b) { if (i64(x += b.x - 2 * mod) < 0) x += 2 * mod; return *this; } Fp &operator-=(const Fp &b) { if (i64(x -= b.x) < 0) x += 2 * mod; return *this; } Fp &operator*=(const Fp &b) { x = reduce(u128(x) * b.x); return *this; } Fp &operator/=(const Fp &b) { *this *= b.inv(); return *this; } Fp operator+(const Fp &b) const { return Fp(*this) += b; } Fp operator-(const Fp &b) const { return Fp(*this) -= b; } Fp operator*(const Fp &b) const { return Fp(*this) *= b; } Fp operator/(const Fp &b) const { return Fp(*this) /= b; } bool operator==(const Fp &b) const { return (x >= mod ? x - mod : x) == (b.x >= mod ? b.x - mod : b.x); } bool operator!=(const Fp &b) const { return (x >= mod ? x - mod : x) != (b.x >= mod ? b.x - mod : b.x); } Fp operator-() const { return Fp() - Fp(*this); } Fp pow(u128 n) const { Fp ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const Fp &b) { return os << b.get(); } friend istream &operator>>(istream &is, Fp &b) { int64_t t; is >> t; b = dynamic_modulo(t); return (is); } Fp inv() const { return pow(mod - 2); } u64 get() const { u64 ret = reduce(x); return ret >= mod ? ret - mod : ret; } static u64 get_mod() { return mod; } }; typename dynamic_modulo::u64 dynamic_modulo::mod, dynamic_modulo::r, dynamic_modulo::n2;
#line 2 "misc/dynamic_modulo.hpp" struct dynamic_modulo { using Fp = dynamic_modulo; using i64 = int64_t; using u64 = uint64_t; using u128 = __uint128_t; static u64 mod; static u64 r; static u64 n2; static u64 get_r() { u64 ret = mod; for (i64 i = 0; i < 5; ++i) ret *= 2 - mod * ret; return ret; } static void set_mod(u64 m) { assert(m < (1LL << 62)); assert((m & 1) == 1); mod = m; n2 = -u128(m) % m; r = get_r(); assert(r * mod == 1); } u64 x; dynamic_modulo() : x(0) {} dynamic_modulo(const int64_t &b) : x(reduce((u128(b) + mod) * n2)){}; static u64 reduce(const u128 &b) { return (b + u128(u64(b) * u64(-r)) * mod) >> 64; } Fp &operator+=(const Fp &b) { if (i64(x += b.x - 2 * mod) < 0) x += 2 * mod; return *this; } Fp &operator-=(const Fp &b) { if (i64(x -= b.x) < 0) x += 2 * mod; return *this; } Fp &operator*=(const Fp &b) { x = reduce(u128(x) * b.x); return *this; } Fp &operator/=(const Fp &b) { *this *= b.inv(); return *this; } Fp operator+(const Fp &b) const { return Fp(*this) += b; } Fp operator-(const Fp &b) const { return Fp(*this) -= b; } Fp operator*(const Fp &b) const { return Fp(*this) *= b; } Fp operator/(const Fp &b) const { return Fp(*this) /= b; } bool operator==(const Fp &b) const { return (x >= mod ? x - mod : x) == (b.x >= mod ? b.x - mod : b.x); } bool operator!=(const Fp &b) const { return (x >= mod ? x - mod : x) != (b.x >= mod ? b.x - mod : b.x); } Fp operator-() const { return Fp() - Fp(*this); } Fp pow(u128 n) const { Fp ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const Fp &b) { return os << b.get(); } friend istream &operator>>(istream &is, Fp &b) { int64_t t; is >> t; b = dynamic_modulo(t); return (is); } Fp inv() const { return pow(mod - 2); } u64 get() const { u64 ret = reduce(x); return ret >= mod ? ret - mod : ret; } static u64 get_mod() { return mod; } }; typename dynamic_modulo::u64 dynamic_modulo::mod, dynamic_modulo::r, dynamic_modulo::n2;