O(1)快速乘

Posted on | Edited on | Comments:

AFO有段时间了，感觉自己什么都不会了，随便研究点东西证明我还活着……

众所周知在long long乘long long模long long的时候，直接乘会溢出，所以要用一些技巧来处理. 一般的快速乘是$O(\log x)$的，所以我们也可以叫它慢速乘. 事实上可以用一些技巧做到$O(1)$，实现真正的快速乘.

首先我们知道$a$模$b$可以表示为$a-b\lfloor a/b\rfloor$，于是如果我们要计算$a\times b$对$m$取模的结果，可以考虑计算$ab-m\lfloor(a/m)*b\rfloor$. 写出下面的代码：

1
2
3
4
a%=MOD; b%=MOD;
ele d=(long double)a/MOD*b+0.5;
ele tmp=a*b-d*MOD;
if (tmp<0) tmp+=MOD;

这里的a*b和d*MOD显然都会溢出，不过可以注意到，溢出只会使结果差$2^{64}$的整数倍，而模出来的结果显然不到$2^{64}$所以一定是对的.

不过这里有一个小问题，为了防止炸精度，我们加了$0.5$来四舍五入，而不是向下取整，最后的结果可能会少一个$m$，所以最后要判断一下，如果tmp<0就要tmp+=MOD.

另外的话如果$a\ge m$或者$b\ge m$可能会挂，所以一开始的时候要模一下.

简化的代码：

1
2
3
4
5
inline ele mul(ele a,ele b,ele MOD){
	a%=MOD; b%=MOD;
	ele tmp=a*b-(ele)((long double)a/MOD*b+0.5)*MOD;
	return tmp<0?tmp+MOD:tmp;
}