倍增思维导图

例子：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

求X^100

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; }

使用快速幂的前提每次变化的规则必须相同，且变化的规则必须满足乘法结合律