【模板】欧拉定理
不会扩展欧拉定理？
十进制快速幂，你值得拥有！！
#include<bits/stdc++.h> #define LL long long #define fr(i,x,y) for(int i=(x);i<=(y);i++) #define rf(i,x,y) for(int i=(x);i>=(y);i--) #define frl(i,x,y) for(int i=(x);i<(y);i++) using namespace std; const int N=20000002; int a,p,n; char c[N]; void read(int &x){ char ch=getchar();x=0; for(;ch<'0'||ch>'9';ch=getchar()); for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0'; } LL qpow(LL a,int n){ LL ans=1; for(LL sum=a%p;n;n>>=1,sum=sum*sum%p) if (n&1) ans=ans*sum%p; return ans; } int main(){ read(a);read(p); scanf("%s",c+1); int n=strlen(c+1); LL sum=a,ans=1; rf(i,n,1){ int x=c[i]-'0'; ans=ans*qpow(sum,x)%p; sum=qpow(sum,10); } cout<<ans<<endl; return 0; }