快速幂,逆元,取模类模板整理。
快速幂
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$ 为质数时，由费马小定理 $a^{m-1}\equiv1\ (mod\ m)$ 知：$a^{m-2}$ 是 $a$ 的逆元。
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;
|