O(1)快速乘

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*bd*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;
}