快速幂（C++）

2024-09-07 05:34:04

 typedef long long LL;

 using namespace std;

 //求a^b%m,递归写法

 LL binaryPow(LL a,LL b,LL m){

 if(b==){    //如果b为0，那么a^0=1

 return ;

 }

 else if(b%2==){    //b为奇数，转换为b-1

 return a*binaryPow(a,b-,m)%m;

 }

 else{    //b为偶数，转换为b/2

 LL mul=binaryPow(a,b/,m);

 return LL*LL%m;

 }

 }

注：上述代码中，条件if(b%2==1)可以用if(b&1)代替，这是因为b&1进行位操作，判断b的末位是否为1.；这样执行速度会快一点

最新文章

热门文章