快速乘详解

两个long long 的数相乘，模一个long long的数，怎么处理？

直接乘是肯定不行的，于是我们就要用到快速乘。

1.用long double

首先，我们知道$a\%b=a-\lfloor \frac{a}{b}\rfloor \times b$，所以$x\times y\%p=x\times y-\lfloor \frac{x\times y}{p}\rfloor \times p$。

这里$x,y,p$都是long long的，显然$x\times y$可能会溢出，但是减去$\lfloor \frac{x\times y}{p}\rfloor \times p$之后的结果肯定是小于$p$的。溢出后减回来结果是一样的。时间复杂度为$O(1)$，适合用于卡常数的题目。

但是，因为long double有精度问题，所以如果数组过大的话返回值就会出问题。

code

long long ch(long long x,long long y,long long p){
	return (x*y-(long long)((long double)x/p*y)*p+p)%p;
}
1
2
3

2.用二进制

与快速幂原理相似，原本$x\times y$为$x+x+x+\cdots +x$连续加$y$个$x$。我们可以优化一下，对于$y$转为二进制中的第$i$位，如果这一位为1，则$ans+=x\times 2^i$。所以只需枚举$i$，具体与快速幂相似，时间复杂度为$O(y)$

code

long long ch(long long x,long long y,long long p){
	long long re=0;
	for(;y;y>>=1,x=(x+x)%p){
		if(y&1) re=(re+x)%p;
	}
	return re;
}
1
2
3
4
5
6
7