Loading [MathJax]/jax/output/HTML-CSS/jax.js

快速幂,逆元,取模类_v2

快速幂,逆元,取模类模板整理。

快速幂

1
2
3
4
5
6
7
8
9
int qmi(int a, int k, int p){
int res = 1;
while(k){
if(k & 1) res = res * a % p;
k >>= 1;
a = a * a % p;
}
return res;
}

逆元

m 为质数时,由费马小定理 am11 (mod m) 知:am2a 的逆元。

1
2
3
int inv(int x){
return qmi(x, mod - 2, mod);
}

取模类

自动实现 mod m 意义下的 +, -, *, / 运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct modint{
int v;
modint(int x) : v((x % mod + mod) % mod) {}

modint operator + (const modint &o){
return modint(v + o.v);
}
modint operator - (const modint &o){
return modint(v - o.v);
}
modint operator * (const modint &o){
return modint(v * o.v);
}
modint operator / (const modint &o){
return modint(v * inv(o.v));
}
};
using Z = modint;