数学--数论--欧拉降幂和广义欧拉降幂（实用好理解）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a,m,b;

inline ll read(ll m){
    register ll x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)){
        x=x*10+ch-'0';
        if(x>=m) f=1;
        x%=m;ch=getchar();
    }
    return x+(f==1?m:0);
}

ll phi(ll n){
    ll ans=n,m=sqrt(n);
    for(ll i=2;i<=m;i++){
        if(n%i==0){
            ans=ans/i*(i-1);
            while(n%i==0) n/=i; 
        }
    }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}

ll fast_pow(ll a,ll b,ll p){
    ll ret=1;
    for(;b;b>>=1,a=a*a%p)
        if(b&1) ret=ret*a%p;
    return ret;
}

int main()
{
    scanf("%lld%lld",&a,&m);
    b=read(phi(m));
    printf("%lld\n",fast_pow(a,b,m));
    return 0;
}