O(log) 快速幂思想
类似于快速幂的思想，把整数 b 用二进制表示，即
那么
因为
O(1) 特殊情况下易精度丢失导致答案错误
利用
首先，当
虽然
Code
#1
// O(1)
ll mul(ll a, ll b, ll p) {
return ((__int128)a*b)%p;
}
// O(1)
ll mul(ll a, ll b, ll p) {
a %= p; b %= p;
ll c = (long double)a * b / p;
ll ans = a * b - c * p;
return (ans % p + p) % p;
}
// O(log)
ll mul(ll a, ll b, ll p) {
ll ans = 0;
while (b) {
if (b & 1) ans = (ans + a) % p;
a = a * 2 % p;
b >>= 1;
}
return ans;
}