Math/modint.cpp

• View this file on GitHub
• Last update: 2020-10-17 00:04:24+09:00

Verified with

• test/aoj/DPL_5_A.test.cpp
• test/aoj/DPL_5_B.test.cpp
• test/aoj/DPL_5_D.test.cpp

Code

#ifndef H_modint
#define H_modint

#include <bits/stdc++.h>

using namespace std;

template<typename T = long long, T Modulus = 1000000007>
class Modint {
public:
  T v;
  constexpr Modint(signed v_) : v(v_) {}
  constexpr Modint(long long v_ = 0) noexcept : v(v_ % Modulus) {
	if (v < 0) v += Modulus;
  }
  Modint pow (long long k) {
	Modint res(1), tmp(v);
	while (k) {
	  if (k & 1) res *= tmp;
	  tmp *= tmp;
	  k >>= 1;
	}	
	return res;
  }
  
  constexpr int getMod() { return Modulus; }
  constexpr Modint operator - () const noexcept {
	return v ? Modulus - v : 0;
  }
  constexpr Modint operator + (const Modint& m) const noexcept { return Modint(*this) += m; }
  constexpr Modint operator - (const Modint& m) const noexcept { return Modint(*this) -= m; }
  constexpr Modint operator * (const Modint& m) const noexcept { return Modint(*this) *= m; }
  constexpr Modint operator / (const Modint& m) const noexcept { return Modint(*this) /= m; }
  constexpr Modint& operator += (const Modint& m) noexcept {
	v += m.v;
	if (v >= Modulus) v -= Modulus;
	return *this;
  }
  constexpr Modint& operator -= (const Modint& m) noexcept {
	v -= m.v;
	if (v < 0) v += Modulus;
	return *this;
  }
  constexpr Modint& operator *= (const Modint& m) noexcept {
	v = v * m.v % Modulus;
	return *this;
  }
  constexpr Modint& operator /= (const Modint& m) noexcept {
	long long a = m.v, b = Modulus, t = 1, u = 0;
	while (b) {
	  long long w = a / b;
	  a -= w * b; swap(a, b);
	  t -= w * u; swap(t, u);
	}
	v = v * t % Modulus;
	if (v < 0) v += Modulus;
	return *this;
  }
  constexpr bool operator == (const Modint& m) const noexcept {
	return this->v == m.v;
  }
  constexpr bool operator != (const Modint& m) const noexcept {
	return this->v != m.v;
  }
  constexpr bool operator < (const Modint& m) const noexcept {
	return this->v < m.v; 
  }
  constexpr bool operator > (const Modint& m) const noexcept {
	return this->v > m.v; 
  }
  friend constexpr ostream& operator << (ostream &os, const Modint<T, Modulus>& x) noexcept {
	return os << x.v;
  }
};

#endif

#line 1 "Math/modint.cpp"



#include <bits/stdc++.h>

using namespace std;

template<typename T = long long, T Modulus = 1000000007>
class Modint {
public:
  T v;
  constexpr Modint(signed v_) : v(v_) {}
  constexpr Modint(long long v_ = 0) noexcept : v(v_ % Modulus) {
	if (v < 0) v += Modulus;
  }
  Modint pow (long long k) {
	Modint res(1), tmp(v);
	while (k) {
	  if (k & 1) res *= tmp;
	  tmp *= tmp;
	  k >>= 1;
	}	
	return res;
  }
  
  constexpr int getMod() { return Modulus; }
  constexpr Modint operator - () const noexcept {
	return v ? Modulus - v : 0;
  }
  constexpr Modint operator + (const Modint& m) const noexcept { return Modint(*this) += m; }
  constexpr Modint operator - (const Modint& m) const noexcept { return Modint(*this) -= m; }
  constexpr Modint operator * (const Modint& m) const noexcept { return Modint(*this) *= m; }
  constexpr Modint operator / (const Modint& m) const noexcept { return Modint(*this) /= m; }
  constexpr Modint& operator += (const Modint& m) noexcept {
	v += m.v;
	if (v >= Modulus) v -= Modulus;
	return *this;
  }
  constexpr Modint& operator -= (const Modint& m) noexcept {
	v -= m.v;
	if (v < 0) v += Modulus;
	return *this;
  }
  constexpr Modint& operator *= (const Modint& m) noexcept {
	v = v * m.v % Modulus;
	return *this;
  }
  constexpr Modint& operator /= (const Modint& m) noexcept {
	long long a = m.v, b = Modulus, t = 1, u = 0;
	while (b) {
	  long long w = a / b;
	  a -= w * b; swap(a, b);
	  t -= w * u; swap(t, u);
	}
	v = v * t % Modulus;
	if (v < 0) v += Modulus;
	return *this;
  }
  constexpr bool operator == (const Modint& m) const noexcept {
	return this->v == m.v;
  }
  constexpr bool operator != (const Modint& m) const noexcept {
	return this->v != m.v;
  }
  constexpr bool operator < (const Modint& m) const noexcept {
	return this->v < m.v; 
  }
  constexpr bool operator > (const Modint& m) const noexcept {
	return this->v > m.v; 
  }
  friend constexpr ostream& operator << (ostream &os, const Modint<T, Modulus>& x) noexcept {
	return os << x.v;
  }
};

Back to top page