O(log) 快速幂思想

类似于快速幂的思想，把整数 b 用二进制表示，即

那么

因为a * 2^i=(a * 2^{i-1}) * 2，若已求出a * 2^{i-1}\text{mod}p，则计算a * 2^{i-1}\text{mod}p时，运算过程中的每一步结果都不超过2 * 10^{18}

O(1) 特殊情况下易精度丢失导致答案错误

利用a * b\text{mod}p = a * b-\lfloor a * b/p \rfloor * p

首先，当a,b < p时，a * b/p下取整以后也一定小于p。我们可以用浮点数执行a * b/p的运算，而不用关心小数点之后的部分。long double 在十进制下有效位为 18~19 位。当浮点数的精度不足以保存精确数值时，它会像科学计数法一样舍弃低位，正好符合我们的要求。

虽然a * b和\lfloor a * b/p \rfloor * p可能很大，但是两者的差一定在 0~p-1之间。所以我们用 long long 来保存a * b和\lfloor a * b/p \rfloor * p各自的记过。整数运算溢出相当于舍弃高位，也正好符合我们的要求。

Code

// 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;
}