题目：求a^b%n (1<=a,b,p<=10^18)
此题用快速幂：采用分治算法将时间复杂度从O(n)降到O(logn)
例如：求2^15 我们先求2^7*2^7*2^1(求2^15) 再求 2^3*2^3*2^1(求2^7) 最后求 2^1*2^1*2^1(求2^3)
让指数不断除以二 b=b/2，当其%2==1，就拿ans=ans*a%n(ans初始为1)
让底数不断相乘，a=a*a%n;
code:
#include<bits/stdc++.h> #pragma GCC optimize(3) #define int long long using namespace std; int a,b,ans=0,p; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch<=‘9‘&&ch>=‘0‘){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } signed main() { int a1,b1; a=read(),b=read(),p=read(); a1=a,b1=b; while(b){ if(b%2==1)ans=(ans*a)%p; a=(a*a)%p; b=b/2; } printf("%lld",ans); return 0; }
原文：https://www.cnblogs.com/nlyzl/p/11371452.html