对于这个问题我也不会证明，只知道是通过拆解然后二进制位运算来化简的，，，菜得一批，背模板吧
#include<algorithm> #include<iostream> #include<cstdio> #include<string> #include<cstring> using namespace std; long long b,p,k,ans=1,t;//b^p mod k int main(){ cin>>b>>p>>k; cout<<b<<"^"<<p<<" mod "<<k<<"="; while(p>0){//次数>0 if(p%2==1){ ans=ans*b%k; } b=b*b%k; p=p>>1; } cout<<ans%k; return 0; }
原文：https://www.cnblogs.com/china-mjr/p/11304407.html