自动搬运

查看原文

来自洛谷，原作者为

	Leap_Frog 是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了

搬运于2025-08-24 21:54:18，当前版本为作者最后更新于2020-09-06 23:16:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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$ 次，证明如下：

• 首先，我们设 $p=\prod_{i=1}^kp_i^{k_i}$，也就是把 $p$ 分解质因数
• 那么 $\phi(p)=p\prod_{i=1}^k\frac{p_i-1}{p_i}$，根据定义得来
• 如果 $p\:\text{mod}\:2=0$，那么上面的连乘符号中有一项为 $\frac12$，于是 $\phi(p)\le\frac12 p$。
• 如果 $p\:\text{mod}\:2=1$，那么连乘符号中肯定存在一位的分子是偶数，于是 $\phi(p)\:\text{mod}\:2=0$

于是如果我们暴力套欧拉定理，那么我们最多进行 $\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;
}

完结撒花