Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- template<int MOD>
- struct ModInt {
- static const int Mod = MOD;
- unsigned x;
- ModInt() : x(0) {}
- ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
- ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
- int get() const { return (int)x; }
- ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
- ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
- ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
- ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
- ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
- ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
- ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
- ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
- ModInt inverse() const {
- signed a = x, b = MOD, u = 1, v = 0;
- while(b) {
- signed t = a / b;
- a -= t * b; std::swap(a, b);
- u -= t * v; std::swap(u, v);
- }
- if(u < 0) u += Mod;
- ModInt res; res.x = (unsigned)u;
- return res;
- }
- bool operator==(ModInt that) const { return x == that.x; }
- bool operator!=(ModInt that) const { return x != that.x; }
- ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement