拓展欧拉定理（自用）

假如说题目给出这种形式(一般是模数 p不会超过 $10^{12}$ ):

a^{b}(mod\ p)

此时 $b$ 非常大,数据量可以到达 $10^{100000}$ 这种程度，我们就不单纯的考虑取模了。这里给出拓展欧拉定理：

a^b \equiv \begin{cases} a^b \mod m & b < \varphi(m) \\ a^{(b \mod \varphi(m)) + \varphi(m)} \mod m & b \ge \varphi(m) \end{cases}

其中 $\varphi(m)$ 表示的是欧拉函数。

欧拉函数 $\varphi(m)$ 表示小于等于 $m$ 的正整数中与 $m$ 互质的数的个数。

ex欧拉定理的使用步骤

计算 $\varphi(mod)$

i64 get(i64 x){
    i64 res=x;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            while(x%i==0) x/=i;
            res-=res/i;
        }
    }
    if(x>1) res-=res/x;
    return res;
}

计算幂数

pair<i64,bool> check(string s,i64 x){
    i64 res=0;
    bool flag=false;
    i64 Mod=get(x);
    for(auto i:s){
        res=res*10+(i-'0');
        if(res>=Mod){
            flag=true;
            res%=Mod;
        }
    }
    return {res,flag};//flag判断ex欧拉定理的取值
}

快速幂计算最终值

void solve(){
    i64 a,p;
    cin>>a;
    string s;
    cin>>s>>p;
    auto [x,y]=check(s,p);
    i64 ans=0;
    i64 phi=0,pls=0;
    pls=get(p);
    if(y){
        x+=pls;
    }
    ans=binpow(a,x,p);
    cout<<ans<<endl;
}

参考题目：

【模板】欧拉函数计算Ⅲ ‖ 降幂公式：扩展欧拉定理_牛客题霸_牛客网