二分指数，直至指数为0
对应地，底数每次平方
这样一来，运算次数至少减少了n-log(2,n)次
一个犇给出了一个从18s优化到0s的过程
<https://blog.csdn.net/qq_19782019/article/details/85621386>
#include<iostream> #define ll long long using namespace std; ll fastpow(ll n,ll a,ll mod) { ll res=1; while(a>0) { if(a&1) res=(res%mod)*(n%mod); a>>=1; n=(n%mod)*(n%mod); } return res%mod; } int main() //求b^p(mod k) { ll b,p,k; ll ans; cin>>b>>p>>k; ans=fastpow(b,p,k); cout<<b<<"^"<<p<<" mod "<<k<<"="<<ans; return 0; }
原文：https://www.cnblogs.com/nightfury/p/13822336.html
