给一个长为 \(n\) 的序列，\(m\) 次操作，每次操作：

1、区间 \([l,r]\) 加 \(x\)

2、对于区间 \([l,r]\)，查询：

\[a[l]^{a[l+1]^{a[l+2]^{\dots ^{a[r]}}}} \pmod p
\]

\(n , m \le 500000\) , 序列中每个数在 \([1,2\cdot 10^9]\) 内，\(p \le 2 \cdot 10^7\) ， 每次加上的数在 \([0,2\cdot 10^9]\) 内

见区间操作，想线段树，但是这道题是可以树状数组的。

首先大家应该知道扩展欧拉定理（EX Euler Theorem)：

\[a^{b} \equiv \left\{\begin{align}
a^{b}\ (b \lt φ(p))\\
a^{b \mod φ(p)+φ(p)}(b \ge φ(p))
\end{align}\right.\pmod{p}
\]

然后我们就可以设计一个递推来处理 \(2\) 操作。

注意，\(b\) 和 \(φ(p)\) 的大小关系不太好判断，我们可以暴力建一个结构体。

数据结构用树状数组

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,m;
int phi[20000003];

namespace bit{
    int t[500005];
    void clear(){memset(t,0,sizeof(t));}
    inline int lowbit(int x){
        return x&(-x);
    }
    int query(int p){
        int res=0;
        while(p){
            res+=t[p];
            p-=lowbit(p);
        }
        return res;
    }
    void update(int p,int v){
        while(p<=n){
            t[p]+=v;
            p+=lowbit(p);
        }
    }
    void update(int l,int r,int v){
        update(l,v);
        update(r+1,-v);
    }
}

void phi_table(int n) {
    memset(phi,0,sizeof(phi));
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!phi[i]) {
            for (int j = i; j <= n; j += i) {
                if (!phi[j]) {
                    phi[j] = j;
                }
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }
}

int qzh[500005];

typedef pair<int,bool> node;

inline node pow(int a,int t,int p){
    node res = make_pair(1,0);
    if(a>=p){a %= p;res.second = 1;}
    while(t){
        if(t&1) res.first *= a;
        if(res.first>=p){res.second = 1;res.first %= p;}a *= a;
        if(a>=p){res.second = 1;a %= p;}t >>= 1;}
    return res;
}

node solve(int l,int r,int x){
    int left=bit::query(l);
    node result;
    if(x==1){
        return make_pair(0,1);
    }
    if(left==1){
        return make_pair(1,0);
    }
    if(l==r){
        return left<x?make_pair(left,0):make_pair(left%x,1);
    }
    int phiv=phi[x];
    result=solve(l+1,r,phiv);
    if(result.second){
        result.first+=phiv;
    }
    return pow(left,result.first,x);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>m;
    phi_table(20000000);
    bit::clear();
    for(int i=1,tmp;i<=n;i++){
        cin>>tmp;
        bit::update(i,i,tmp);
    }
    while(m--){
        int op,l,r,p;
        cin>>op>>l>>r>>p;
        if(op==1){
            bit::update(l,r,p);
        }
        else{
            cout<<solve(l,r,p).first<<'\n';
        }
    }
    return 0;
}