对于long long范围下模意义的乘法，我们需要快速乘防止溢出
\(O(logn)\) 快速乘
类比快速幂
1
2
3
4
5
6
7
8
| inline LL mul(LL a, LL b, LL p) {
LL ans = 0;
while (b) {
if (b & 1) ans = (ans + a) % p;
a = (a + a) % p, b >>= 1;
}
return ans;
}
|
\(O(1)\) 快速乘 #1
利用long double
1
2
3
| inline LL mul(LL a, LL b, LL p) {
return (a * b - (LL)((long double)a / p * b) * p + p) % p;
}
|
\(O(1)\) 快速乘 #2
利用位运算
1
2
3
4
5
| inline LL mul(LL a, LL b, LL p) {
LL lf = a * (b >> 25LL) % p * (1LL << 25) % p;
LL rg = a * (b & ((1LL << 25) - 1)) % p;
return (lf + rg) % p;
}
|