快速幂的几种不同范例:
NO.1:(递归式)
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; int ksm(int a,int b,int n) { int t; if (b == 0) return 1; if (b == 1) return a%n; t = ksm(a, b/2, n); t = t*t % n; if (b%2) { t = t*a % n; } return t; } int main() { freopen("ksm.in","r",stdin); freopen("ksm.out","w",stdout); long long a,b,c; cin>>a>>b>>c; long long ans=ksm(a,b,c); cout<<ans<<endl; return 0; }
NO.2:(非递归式)
#include <iostream> #include <cstdio> using namespace std; int modexp(int a,int b,int n) { int ret=1; while(b) { if(b%2) ret=ret*a%n; a=(a*a)%n; b>>=1; } return ret; } int main() { freopen("ksm.in","r",stdin); freopen("ksm.out","w",stdout); long long a,b,c; cin>>a>>b>>c; long long ans=modexp(a,b,c); cout<<ans<<endl; return 0; }
NO.3:(你懂的)
long long ans=1; void ksm(long long a,long long b,long long c,long long &ans) { for(;b;b/=2,a=(a*a)%c) if(b&1) ans=(ans*a)%c; }