例子:1->2->4->8->16->32->64->128即2^0->2^1->2^2->2^3->2^4->2^5->2^6->2^7
倍增一次就是X*X,即X^1* X^1= X^2再倍增一次就是让X^2自乘,X^2*X^2=X^4
100可以由1,2,4,8......,2^n中的某几个相加获得。分析可得:100=4+32+64
求2^100,可以拆分为2^64* 2^32 *2^4
#include<bits/stdc++.h>
using namespace std;
int main(){
long long a,b,c,ans=1;
scanf("%lld%lld%lld",&a,&b,&c);
while(b){
if(b%2==1) ans=ans*a%c;
a=a*a%c;
b/=2;
}
printf("%lld",ans);
return 0;
}
使用快速幂的前提每次变化的规则必须相同,且变化的规则必须满足乘法结合律