快速乘
O(log) 快速幂思想
类似于快速幂的思想，把整数 b 用二进制表示，即
$math_inline$b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+...+c_{0}2^{0}$math_inline$那么
$math_inline$a * b=c_{k-1} * a * 2^{k-1}+c_{k-2} * a * 2^{k-2}+...+c_{0} * a * 2^{0}$math_inline$因为 $math_inline$a * 2^i=(a * 2^{i-1}) * 2$math_inline$ ，若已求出 $math_inline$a * 2^{i-1}\text{mod}p$math_inline$ ，则计算 $math_inline$a * 2^{i-1}\text{mod}p$math_inline$ 时，运算过程中的每一步结果都不超过 $math_inline$2 * 10^{18}$math_inline$
O(1) 特殊情况下易精度丢失导致答案错误
利用 $math_inline$a * b\text{mod}p = a * b-\lfloor a * b/p \rfloor * p$math_inline$
首先，当 $math_inline$a,b < p$math_inline$ 时， $math_inline$a * b/p$math_inline$ 下取整以后也一定小于 $math_inline$p$math_inline$ 。我们可以用浮点数执行 $math_inline$a * b/p$math_inline$ 的运算，而不用关心小数点之后的部分。long double 在十进制下有效位为 18~19 位。当浮点数的精度不足以保存精确数值时，它会像科学计数法一样舍弃低位，正好符合我们的要求。
虽然 $math_inline$a * b$math_inline$ 和 $math_inline$\lfloor a * b/p \rfloor * p$math_inline$ 可能很大，但是两者的差一定在 0~p-1之间。所以我们用 long long 来保存 $math_inline$a * b$math_inline$ 和 $math_inline$\lfloor a * b/p \rfloor * p$math_inline$ 各自的记过。整数运算溢出相当于舍弃高位，也正好符合我们的要求。
Code
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;
}