同余类

给定一个正整数 $n$ ，将所有整数依据模 $n$ 的余数 $r\in[0,n-1]$ 分为 $n$ 类，其中每一类都可以被表示为 $C_r=nx+r$ ，一个 $C_r$ 构成的一个集合是模 $n$ 的一个同余类

完全剩余系

给定一个正整数 $n$ ，有 $n$ 个不同的模 $n$ 的同余类，从这 $n$ 个同余类中各选出一个元素共计 $n$ 个数，这些数构成的一个集合为模 $n$ 的一个完全剩余系。显然对于正整数 $n$ 一定存在一个完全剩余系是 $Z_n=[0,n-1]$ ，该剩余系为简单完全剩余系。同理，对剩余系中任意元素加上 $n$ 的整数倍后得到的集合仍然为模 $n$ 的一个完全剩余系

简化剩余系

给定一个正整数 $n$ ，有 $\varphi(n)$ 个不同的模 $n$ 的余数 $r$ 与 $n$ 互质的同余类，在这 $\varphi(n)$ 个同余类中各选出一个元素共计 $\varphi(n)$ 个数，这些数构成的一个集合是模 $n$ 的一个简化剩余系。其中 $\varphi(n)$ 为 $n$ 的欧拉函数

$$ \varphi(n)=n\times \prod_{i=1}^s \frac{p_i-1}{p_i} $$

欧拉定理

若 ${\rm{gcd}}(a,m)=1$，则 $a^{\varphi(m)} \equiv 1({\rm{mod}}\ m)$

简单证明：

设 $\{r_1,r_2,\cdots ,r_{\varphi(m)} \}$ 是一个模 $m$ 的简化剩余系，则 $\{ar_1,ar_2,\cdots,ar_{\varphi(m)} \}$ 也是模 $m$ 的一个简化剩余系，所以有

$$ \prod_{i=1}^{\varphi(m)} r_i\equiv \prod_{i=1}^{\varphi(m)} ar_i \equiv a^{\varphi(m)}\prod_{i=1}^{\varphi(m)} r_i ({\rm{mod }}\ m) $$

同余式两侧约去 $\prod_{i=1}^{\varphi(m)} r_i$ 后得

$$ a^{\varphi(m)} \equiv 1({\rm{mod}}\ m) $$

当 $m$ 为质数时 $\varphi(m)=m-1$ ，得到费马小定理 $a^{m-1}\equiv 1({\rm{mod}}\ m)$

扩展欧拉定理

$$ a^b=\left\{ \begin{array}{l} a^{b\ {\rm{mod}}\ \varphi(m)} & {\rm{gcd}}(a,m)=1 &({\rm{mod}}\ m) \\ a^b&b<\varphi(m),{\rm{gcd}}(a,m)\ne1 &({\rm{mod}}\ m) \\ a^{b\ {\rm{mod}}\ \varphi(m)+\varphi(m)} &b\ge\varphi(m),{\rm{gcd}}(a,m)\ne1&({\rm{mod}}\ m) \end{array} \right. $$

计算 $a^b$ 时，若 $b$ 较小，直接跑一遍快速幂即可，否则先用扩展欧拉定理进行降幂再跑快速幂

对于单独的 $b$ 来说，利用试除法比筛法更加优秀

LL get_phi(LL n){
    LL res=n;
    for (LL i=2;i*i<=n;i++){
        if (n%i==0){
            res=res*(i-1)/i;
            while (n%i==0)
                n/=i;
        }
    }
    if (n>1) res=res*(n-1)/n;
    return res;
}

对 $b$ 进行降幂操作，因为 $a^{\varphi(m)} \equiv 1\to a^{b\ {\rm{mod}}\ \varphi(m)}\equiv a^{b\ {\rm{mod}}\ \varphi(m)+\varphi(m)}({\rm{mod}}\ m)$ ，所以不需要单独判断

LL depow(LL phi,string b){
    LL res=0;
    bool f=0;//判断b和phi_m的大小关系
    for (auto c:b){
        res=res*10+(c-'0');
        if (res>=phi) f=1,res%=phi;
    }
    if (f) res+=phi;//如果b>phi_m则需要加上phi_m
    return res;
}

以洛谷P5091为例：https://www.luogu.com.cn/problem/P5091、

LL ksm(LL a,LL b,LL p){
    LL res=1;
    while (b){
        if (b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}

LL get_phi(LL n){
    LL res=n;
    for (LL i=2;i*i<=n;i++){
        if (n%i==0){
            res=res*(i-1)/i;
            while (n%i==0)
                n/=i;
        }
    }
    if (n>1) res=res*(n-1)/n;
    return res;
}

LL depow(LL phi,string b){
    LL res=0;
    bool f=0;
    for (auto c:b){
        res=res*10+(c-'0');
        if (res>=phi) f=1,res%=phi;
    }
    if (f) res+=phi;
    return res;
}

void solve(){
    LL a,m;
    string b;
    cin>>a>>m>>b;
    cout<<ksm(a,depow(get_phi(m),b),m)<<endl;
}