快速幂,逆元,取模类模板整理。
快速幂
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 为质数时,由费马小定理 am−1≡1 (mod m) 知:am−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;
|