快速幂

思想

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

当我们计算 XymodPX^y mod P时,我们可以把yy以二进制的形式拆分

12=2+8;12=2+8 ;

5=1+4;5=1+4 ;

19=1+2+1619=1+2+16

于是……

519=51525165^{19} = 5^1 * 5^2 * 5^{16}

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

具体操作

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

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}