欧拉定理:
当(a),(m)互质时,(a^{phi(m)}equiv 1 (mod ~ m))
扩展欧拉定理:
当(B>phi(m))时,(a^Bequiv a^{B~mod~phi(m)+phi(m)})
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
int a,m,b;
bool flag;
inline int read(int MOD){
int x=0; char c=getchar();
while(c<'0') c=getchar();
while(c>='0'){
x=x*10+c-'0';
if(x>MOD) flag=1,x%=MOD;
c=getchar();
}
return x;
}
inline int mul(int x,int y,int MOD){
int s=0;
while(y){
if(y&1) s=(s+x)%MOD;
y>>=1;
x=(x+x)%MOD;
}
return s;
}
inline int qpow(int x,int k,int MOD){
int s=1ll%MOD;
while(k){
if(k&1) s=mul(s,x,MOD);
k>>=1;
x=mul(x,x,MOD);
}
return s;
}
signed main()
{
scanf("%lld%lld",&a,&m);
int phi=m;
int k=sqrt(m),x=m;
for(int i=2;i<=k;++i)
if(x%i==0){
while(x%i==0) x/=i;
phi=phi/i*(i-1);
}
if(x!=1) phi=phi/x*(x-1);
b=read(phi);
if(flag)
printf("%lld
",qpow(a,b+phi,m));
else printf("%lld
",qpow(a,b,m));
return 0;
}