快速乘

两个数直接乘爆 ( ext{long long}) 怎么办 ?

使用快速乘

先来个 (O(1)) 快速乘

LL fastMulMod(LL x, LL y, LL mod) {
	return (x * y - (LL)((long double)x * y / mod) * mod + mod) % mod;
}

首先假如不会溢出的话, 后面两项都被模掉了就只剩 x * y 了对吧

后面的 (lfloor frac {xy} {mod} floor imes mod) 就是巧妙的把溢出的减掉了感性理解, 使答案在 ( ext{long long}) 范围内

---

假如怕有精度误差的话其实可以使用 ( ext{__int128}) 来实现 (O(1)) 快速乘 (实测比 ( ext{long double}) 慢)

LL fastMulMod(LL x, LL y, LL mod) {
	return static_cast<__int128>(1) * x * y % mod;
}

---

但 ( ext{__int128}) 在联赛中并不能用, 那我就再贴个 (O(logn)) 快速乘, 也是最常见的快速乘

LL fastMulMod(LL x, LL y, LL mod) {
	LL res = 0;
	while(x) {
		if(x & 1) res = (res + y) % mod;
		y = (y << 1) % mod, x >>= 1;
	}
}

本质上是运用了乘法分配率, 没什么好讲的