给定三个正整数a,b,m,求a^b%m
这里当a和b的范围比较小时,就可以直接只用循环来进行计算,但是当a和b的范围很大时,使用循环就很消耗时间了。
在这里就可以使用快速幂的做法,它是基于二分的思想。使用快速幂针对这道题的思路是:
1)如果b是奇数,则a^b = a * a^(b-1)
2)如果b是偶数,则a^b = a^(b/2) * a^(b/2)
所以我们就可以使用递归的方法来求解这道题。
typedef long long LL;
LL binaryPow(LL a,LL b,LL m){
if(b==0){
return 1;
}
else if(b%2==0){ //当为偶数时
int mul=binaryPow(a,b/2,m);
return mul*mul%m;
}
else{ //当为奇数时
return a*binaryPow(a,b-1,m);
}
}
版权所有:可定博客 © WNAG.COM.CN
本文标题:《二分的思想与快速幂》
本文链接:https://cloud.tencent.com/developer/article/1616933
特别声明:除特别标注,本站文章均为原创,本站文章原则上禁止转载,如确实要转载,请电联:wangyeuuu@qq.com,尊重他人劳动成果,谢过~