P3934[Ynoi2016]炸脖龙I（题解）

· · 题解

P.S.

人生第一道由乃OI的题啊（自上次那道区间sin和被踢出Ynoi后）。
个人觉得细节还是蛮多的QAQ（虽然代码不长）。
奈芙莲最可爱了，比珂朵莉可爱多了。

Discription.

给定一个序列，设函数 f(i,i)=a_i,f(i,j)=a^{f(i+1,j)}。
支持区间加，查询 f(l,r)\:\text{mod}\:p\quad(l\le r)。
（原题中是用连指数表示的，这里用了递归定义的方法，希望读者能看得明白
（笔者刚开始一直以为是 {(a^b)}^c，手模样例模了半天。

Problem.

看上去好像很小清新的，其实却是带毒瘤。
这题是道区间询问，一看就很像线段树。
但是我们却发现 f(i,j)\not=f(i,k)^{f(k+1,j)}（这也是笔者刚开始犯的错误之一。
众所周知，线段树维护的东西需要满足区间可加性，所以这题无法用线段树维护。
那么怎么办呢？我们请出最可爱的奈芙莲树！（奈芙莲最可爱了

Part. 0 奈芙莲美图欣赏！感觉要被珂学家D没，不过奈芙莲最可爱了

Part. 1 奈芙莲树简介

用于解决的问题：好像范围其实挺小的，应该就只有这题了吧。
名字由来：Nephren Ruq Insania
前置知识：扩欧好吧是扩展欧拉定理
前置知识：树状数组2，线性筛筛phi
不会吧不会吧，不会真有人不会树状数组就爆切由乃OI吧。
接下来的叙述中默认读者已经掌握了它（笔者太菜，不会证明

Part. 2 奈芙莲树具体实现

首先，我们回顾一下目的：我们需要求 f(l,r)\: \text{mod}\: p。
我们套上扩展欧拉定理：它等于 a_l^{f(l+1,r)\:\text{mod}\:p+[f(l+1,r)\ge \phi(p)]\times \phi(p)}
（中间那个是艾弗森括号
于是我们就把 f(l,r)\:\text{mod}\:p 转化成了 f(l+1,r)\:\text{mod}\: \phi(p)（当然中间还要分类讨论
我们可以证明：p\rightarrow\phi(p)这样的迭代只会进行 \log p 次，证明如下：

于是如果我们暴力套欧拉定理，那么我们最多进行 \log 次迭代。
所以暴力的复杂度是对的！

接下来就是代码实现问题了，因为扩展欧拉定理中需要大量分类讨论。
我们也需要进行一定量的分类讨论来解决这道题。
1、如果 \exists i\in[l,r],a_i=1，那么 f(l,r)=f(l,i)，因为 1^k=1,k\in \mathbb{N}
2、那么 \forall i\in[l,r],a_i\ge2，所以 f(l,l+5)\le2^{2^{2^{2^{2^{}}}}}=2^{65536}\ge 2\times10^7\ge p。
　　所以如果区间长度大于 5 且其中没有一个 1，那么这个区间的值肯定大于 p，我们成功的避免了分类讨论。

于是我们只需要对于每个区间，暴力处理出第二位到第六位。
（因为第一位是底数，我们想要判断的是指数和模数的关系
如果这五位的值大于 P，那么直接递归处理。
否则直接计算答案就好了。

完结撒花，最后来一遍：奈芙莲最可爱了！

Coding.

//不会，我并没有做什么需要让你道谢的事 ——Nephren
//奈芙莲最可爱了！奈芙莲比珂朵莉可爱多了。
//众所周知，威莲是指威廉和莲，所以威廉和莲是官配！
//上面这些忽略就好了，怕引战（
#include<bits/stdc++.h>
#define ri register
using namespace std;typedef long long ll;//这些应该没什么好解释的
const int N=500005,M=20000005;int Q,n,ph[M],p[M/10],id;ll t[N];char v[M];inline ll qry(int x);
struct node{ll v[N];int l[N];inline ll& operator[](int x) {return l[x]==id?v[x]:(l[x]=id,v[x]=qry(x));}}a;
//上面是树状数组支持区间修改单点查询，这个总应该都会了吧。
//这里我重定义了[]，用起来方便一点，而且l是用来卡常的，id在下面树状数组修改用
inline int read()
{//快读，不解释
    ri char c=getchar(),f=0;ri int t=0;
    for(;c<'0'||c>'9';c=getchar()) if(!(c^45)) f=1;
    for(;c>='0'&&c<='9';c=getchar()) t=(t<<1)+(t<<3)+(c^48);
    return f?-t:t;
}
inline void write(int x)
{//快输，不解释
    static int t[25];ri int tp=0;
    if(x==0) return(void)(putchar('0'));else if(x<0) putchar('-'),x=-x;
    while(x) t[tp++]=x%10,x/=10;
    while(tp--) putchar(t[tp]+48);
}
inline void add(ri int x,ri ll y) {id++;for(;x<=n;x+=(x&(-x))) t[x]+=y;}
//树状数组修改，id表示当前是第几次修改，呼应上文减小常数处
inline ll qry(ri int x) {ri ll r=0;for(;x;x-=(x&(-x))) r+=t[x];return r;}
//树状数组查询（用了差分的思想，不想解释
inline int ksm(ri ll x,ri ll q,ri int P) {x%=P;int r=1;for(;q;q>>=1,x=1ll*x*x%P) if(q&1) r=1ll*r*x%P;return r%P;}
//快速幂，注意点：x要开ll，x一进去就要取模，q一定要开ll，因为这个调自闭了
inline void William()
{//初始化线性筛phi[]，函数名威连
    ri int pc=0;ph[1]=1;
    for(int i=2;i<M;i++)
    {
        if(!v[i]) p[++pc]=i,ph[i]=i-1;
        for(int j=1;j<=pc&&p[j]*i<M;j++) {v[p[j]*i]=1,ph[p[j]*i]=ph[i]*(i%p[j]?p[j]-1:p[j]);if(i%p[j]==0) break;}
    }
}
inline void Neph(int l,int r,int c) {add(l,c),add(r+1,-c);}
//Nephren前半段，区间修改（差分
inline int ren(int l,int r,int P)
{//Nephren后半段，区间查询查询f(l,r)%P
    if(a[l]%P==0) return 0;else if(P==1) return 1;else if(l==r) return a[l]%P+(a[l]>=P?P:0);
//一大堆特判，应该没什么好解释的了吧，只要仔细阅读上文应该就能懂
    int ls=min(l+5,r);for(int i=l+1;i<=ls;i++) if(a[i]==1) {ls=i;break;}ll g=0,la=a[ls];
//暴力枚举前5位，注意r可能小于l+5，找到最左边的a[i]=1的位置。
    for(int i=ls-1;i>=l+1;i--) {g=la,la=1;while(g--) {la*=a[i];if(la>ph[P]) return ksm(a[l],ren(l+1,r,ph[P])+ph[P],P);}}
//对，你没看错，连快速幂都不需要直接暴力while就好了
    return ksm(a[l],la,P);//如果前五位小于l，那么就直接return快速幂
}
signed main()
{
    n=read(),Q=read(),id=0,William();//读入，初始化
    for(ri int i=1;i<=n;i++) scanf("%lld",&a[i]),add(i,a[i]-a[i-1]);
//读入，因为上面重定义[]时用了引用，所以可以直接读入
    for(ri int fg,l,r,c;Q--;)
    {
        fg=read(),l=read(),r=read(),c=read();
        if(fg==1) Neph(l,r,c);else write(ren(l,r,c)%c),putchar('\n');
    }
    return 0;
}

完结撒花