快速幂——递归和迭代两种写法

1 递归写法

//递归写法 
ll binaryPow1(ll a,ll b,ll m){if(b==0) return 1;	//如果b为0，那么a^0=1//b为奇数，转换为b-1 if(b%1==1) return a*binaryPow1(a,b-1,m)%m;else{ll mul=binaryPow1(a,b/2,m);return mul*mul%m;} 
}

2 迭代写法

//迭代写法
ll binaryPow2(ll a,ll b,ll m){ll ans=1;while(b>0){if(b&1){	//如果b的二进制末尾为1 ans=ans*a%m;	//ans乘上a }a=a*a%m;	//令a平方 b>>=1;		//令b的二进制右移一位 }return ans;
}