自动搬运

查看原文

来自洛谷，原作者为

	sxyugao **

搬运于2025-08-24 22:04:54，当前版本为作者最后更新于2018-09-27 08:42:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更好的阅读体验

怎么没人发快速乘的版本啊，那我就来水一发吧，其余思想如BSGS不再赘述。

为什么要快速乘？模数$>\sqrt{2^{63}-1}$，直接乘会爆$long\;long$。

正常的快速乘：

LL mul(LL a, LL b, LL P){
	LL ans = 0;
	for(; b; b >>= 1, (a <<= 1) %= P)
		if(b & 1) (ans += a) %= P;
	return ans;
}

这是基于快速幂思想的，所以复杂度为 $log$，常数爆炸，会愉快地TLE，所以有一篇题解称之为“龟速乘”。

接下来是一份神奇的快速乘:

LL mul(LL a, LL b, LL P){
    LL L = a * (b >> 25LL) % P * (1LL << 25) % P;
    LL R = a * (b & ((1LL << 25) - 1)) % P;
    return (L + R) % P;
}

是不是看起来超级牛逼，一堆位运算。。。

其实看着这么高级其实就是利用了小学生都会的乘法分配律。

我们要计算 $a \cdot b\;mod\;p$，设 $b=L+R$。

那么原式就变为为$a\cdot(L+R)\;mod\;p=((a\cdot L)\;mod\;p+(a\cdot R)\;mod\;p)\;mod\;p$。

我们把 $L$ 钦定为 $b$ 的二进制前 $x$ 位，$R$ 为 $b$ 的后 $(64-x)$ 位。

就得到了以上的代码（以上这份代码 $x=25$），复杂度近似为O(1)。

用上这样的快速乘就可以AC了。

参考链接：https://zhuanlan.zhihu.com/p/31872064

完整代码及BSGS推导

欢迎大佬来访 (✧◡✧)