国庆的时候鸽了几天，今天又开始写闲话了。

收到了最近机房里的猪国杀浪潮，今天下午我把我的猪国杀重构了一下，然后又调了一天。（悲）

这是成果（放图）

读61-65行。

奈芙莲树

据说还有威廉树，然而并不清楚是什么。

其实就是树状数组和扩展欧拉定理的（无）有机结合

以及奈芙莲树似乎就只在本题（还有相逢是问候?）中使用过

[Ynoi2016] 炸脖龙 I

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

1、区间[l,r]加x

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

\(a[l]^{a[l+1]^{a[l+2]^{\dots ^{a[r]}}}} \mod p\)

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

做法：

幂塔显然要用扩欧处理，递归深度是\(\ln(p)\)级别的。然而扩欧的一个很严格的限制是幂一定要大于\(\phi(p)\)。

我们发现，$2^{2{2^{22}}} $已经大于2e7，因此我们只要爆判五个数就可以。

注意到区间修改，我们可以用一个树状数组维护区间修改，单点查询。。

总复杂度\(O(m\log^2(n))\)

贴代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int maxn = 20000005;
int phi[maxn],prime[maxn],cnt,n,m;
bool vis[maxn];
#define LL long long
void init(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j])phi[i*prime[j]]=phi[i]*(prime[j]-1);
            else{
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
        }
    }
}
struct BIT
{
    LL c[1000006];
    int lowbit(int x){return x&(-x);}
    void add(int x,LL w)
    {
        while(x<=n)
        {
            c[x]+=w;
            x+=lowbit(x);
        }
    } 
    void upd(int l,int r,LL w)
    {
        add(l,w);
        add(r+1,-w);
    }
    LL ask(int x)
    {
        LL ret=0;
        while(x)
        {
            ret+=c[x];
            x-=lowbit(x);
        }
        return ret;
    }  
}a;
LL fsp(LL a,LL b,LL p)
{
    LL s=1;
    a%=p;
    while(b)
    {
        if(b&1)s=1ll*s*a%p;
        b>>=1ll;
        a=1ll*a*a%p;
    }
    return s;
}
pair<LL,bool> ksm(LL a,LL b,LL p)
{
    LL s=1;
    bool flag=0;
    if(a>p&&b!=0)
    {
        flag=1;
        a%=p;
    }
    while(b)
    {
        if(b&1)
        {
            s=s*a;
            if(s>p)
            {
                flag=1;
                s%=p;
            }
        }
        b>>=1;
        a=a*a;
        if(a>p&&b!=0)
        {
            flag=1;
            a%=p;
        }
    }
    return {s,flag};
}
LL baolichuli(LL l,LL &r,LL p)
{
    if(a.ask(l)%p==0)return 0;
    for(int i=l+1;i<=min(l+6,r);i++)
    {
        if(a.ask(i)==1)
        {
            r=i;
            break;
        }
    }
    LL s=1;
    for(int i=min(l+6,r);i>=l+1;i--)
    {
        pair<LL,bool> b=ksm(a.ask(i),s,phi[p]); 
        if(b.second==1) return fsp(a.ask(l),baolichuli(l+1,r,phi[p])+phi[p],p);
        s=b.first;
    }
    if(s>phi[p])return fsp(a.ask(l),baolichuli(l+1,r,phi[p])+phi[p],p);
    return fsp(a.ask(l),s,p);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    init(20000000);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        LL x;
        cin>>x;
        a.upd(i,i,x);
    }
    int cnt=0;
    for(int i=1;i<=m;i++)
    {
        LL opt,l,r,p;
        cin>>opt>>l>>r>>p;
        if(opt==1)
        {
            a.upd(l,r,p);
        }else{
            cnt++;
            LL k=baolichuli(l,r,p);
            cout<<k<<endl;
        }

    }
    return 0;
}