各种快速乘黑科技

方法一

沿用快速幂的方法，将乘法改为加法，时间复杂度$O(\log b)$

LL Quick_Mul(LL a,LL b,LL p) {
	LL sum=0;
	for(; b; b>>=1,a=(a+a)%p)if(b&1)sum=(sum+a)%p;
	return sum;
}

方法二

利用乘法分配律将乘数分为两部分依次累加进入答案。
此方法要求$p\lt2^{32}$，否则依然会溢出。

const LL LIMIT=1e6;

LL Quick_Mul(LL a,LL b,LL p) {
	LL a1=a/LIMIT,a2=a%LIMIT,b1=b/LIMIT,b2=b%LIMIT;
	return ((((a1*b1%p*LIMIT%p*LIMIT%p)+(a1*b2%p*LIMIT%p))%p+(a2*b1%p*LIMIT%p))%p+(a2*b2%p))%p;
}

方法三

暴力出奇迹！
此方法要求平台支持__int128

LL Quick_Mul(__int128 a,__int128 b,__int128 p) {
	return a*b%p;
}

方法四

转成long double进行运算。
缺点是可能会有精度问题。

LL Quick_Mul(LL a,LL b,LL p) {
	LL tmp=(a*b-(LL)((long double)a/p*b+1e-8)*p);
	if(tmp<0)return tmp+p;
	else return tmp;
}