实现一个整数取模类(加减乘除均可)。
template<int Mod, typename T = int> class ModInteger {
private:
T x; // 数值本身,类型默认为 int
private:
static T increase(const T &num) { return num >= Mod ? num - Mod : num; }
static T decrease(const T &num) { return num < 0 ? num + Mod : num; }
public:
ModInteger() : x(0) { }
ModInteger(T num) : x(num >= 0 ? num % Mod : (Mod - (-num) % Mod) % Mod) { }
ModInteger inverse() const {
T a = x, u = 1, v = 0, k = 0; // 扩展欧几里得求逆元
int b = Mod;
while (b > 0) {
k = a / b;
swap(a -= k * b, b);
swap(u -= k * v, v);
}
return ModInteger(u);
}
static ModInteger pow(ModInteger a, ll b) {
ModInteger res(1); // 快速幂,静态成员函数,可直接在外部调用。
while (b) {
if (b & 1) res *= a;
a *= a;
b >>= 1;
}
return res;
}
ModInteger pow(ll b) const { return pow(*this, b); } // 快速幂,成员函数。
ModInteger operator-() const { return ModInteger(-x); }
ModInteger &operator+=(const ModInteger &rhs) { x = increase(x + rhs.x); return *this; }
ModInteger &operator-=(const ModInteger &rhs) { x = decrease(x - rhs.x); return *this; }
ModInteger &operator*=(const ModInteger &rhs) { x = 1ll * x * rhs.x % Mod; return *this; }
ModInteger &operator/=(const ModInteger &rhs) { *this *= rhs.inverse(); return *this; } // 除以就相当于乘以逆元
friend ModInteger operator+(const ModInteger &lhs, const ModInteger &rhs) { return ModInteger(lhs) += rhs; }
friend ModInteger operator-(const ModInteger &lhs, const ModInteger &rhs) { return ModInteger(lhs) -= rhs; }
friend ModInteger operator*(const ModInteger &lhs, const ModInteger &rhs) { return ModInteger(lhs) *= rhs; }
friend ModInteger operator/(const ModInteger &lhs, const ModInteger &rhs) { return ModInteger(lhs) /= rhs; }
bool operator==(const ModInteger &rhs) const { return x == rhs.x; }
bool operator!=(const ModInteger &rhs) const { return x != rhs.x; }
bool operator>=(const ModInteger &rhs) const { return x >= rhs.x; }
bool operator<=(const ModInteger &rhs) const { return x <= rhs.x; }
bool operator>(const ModInteger &rhs) const { return x > rhs.x; }
bool operator<(const ModInteger &rhs) const { return x < rhs.x; }
T data() const { return x; } // 获取数值
friend ostream &operator<<(ostream &os, const ModInteger &num) { return os << num.x; }
friend istream &operator>>(istream &is, ModInteger &num) {
T input;
is >> input;
num = ModInteger(input);
return is;
}
};
标签:ModInteger,const,rhs,整数,取模类,num,operator,return
From: https://www.cnblogs.com/jxyanglinus/p/18528981