（扩展）欧拉定理

（扩展）欧拉定理

练一手板子题啦！

欧拉定理：当 $a,m$a,m互质时，有
${\displaystyle a^b\equiv a^{b\%\phi \left(m\right)}\left(modm\right)}$ab≡ab%φ(m) (mod m)

扩展欧拉定理：当 $a,m$a,m不一定互质时，有
{ab≡ab ( mod m ), b<φ(m)ab≡ab%φ(m)+φ(m) ( mod m ),b≥φ(m)​

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const int maxn = 3e5+7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;

int main() {
    int a=read(), m=read();
    string b; cin>>b;
    int phi=1, M=m;
    for(int i=2; i*i<=M; ++i) {
        if(M%i==0) {
            M/=i; phi*=i-1;
            while(M%i==0) phi*=i, M/=i;
        }
    }
    if(M>1) phi*=M-1;
    int k=0, f=0;
    for(char c: b) {
        k=k*10+c-'0';
        if(k>=phi) k%=phi, f=1;
    }
    if(f) k+=phi; //只有当b>=phi(m)时才加一个
    ll ans=1;
    while(k) {
        if(k&1) ans=ans*a%m;
        a=ll(a)*a%m, k>>=1;
    }
    printf("%lld\n", ans);
}