O(1) 快速乘

有一些毒瘤题,数据大小不光会炸(int),有时甚至会炸(long long)。这时一个(O(1))的防爆乘就很重要了

(a*b%p)可以转化为(a*b-[a*b/p]*p) 这里用了(long double)舍弃低位保留18位的特性

最后不要忘记特判

inline ll C(ll a,ll b,ll p){
	a%=p,b%=p;
	ll c=a*b-(ll)((long double)a*b/p+0.5)*p;
	return c<0?c+p:c;
}
原文地址:https://www.cnblogs.com/nianheng/p/9927876.html