快速幂

思想

快速幂是一个快速计算一个数的幂次方的算法(废话)

当我们计算 $X^y mod P$时，我们可以把$y$以二进制的形式拆分

例 $12=2+8$;

$5=1+4$ ;

$19=1+2+16$

于是……

$5^{19} = 5^1 * 5^2 * 5^{16}$

这样，我们就可以每次将$x$做平方操作，到达所需要的值时即可更新$ans$，时间复杂度$O(logn)$

具体操作

我们可以使用$y$&$1$来获取$y$的二进制的最后一位，使用$y>>=1$来使$y$的二进制向右移，由于C++会在右移后的高位补0，所以在操作完后，$y$的值会变为0，所以当$y$等于0时跳出循环并返回$ans$

代码实现

int qpow(int x,int y,int mod) //x为底数，y为幂，mod为模数
{
	int ans=1;
	while(y)
	{
		if(y&1)
		{
			ans*=x;
			ans%=mod;
		}
		y>>=1;
		x*=x;
		x%=mod;
	}
	return ans;
}