前置芝士：扩展欧拉定理
题目大意
给一个长为 \(n\) 的序列，\(m\) 次操作，每次操作：
- 区间 \([l,r]\) 加 \(x\)；
- 对于区间 \([l,r]\)，查询：
\[{a_l}^{{a_{l+1}}^{{a_{l+2}}^{{\dots} ^{a{r}}}}} \mod p
\]
思路
首先我们有：
\[a^k\equiv \left\{\begin{matrix}a^k, & k<p\\ a^{(k\bmod {\varphi(p)})+\varphi(p)}, & k\ge p\end{matrix}\right.\ \pmod p
\]
注意到这两个情况不可以合并，可以举出反例：\(a=2,k=2,p=16\) 时，\(a^k \bmod p =4\)，而 \(a^{(k\bmod \varphi(p))+\varphi(p)} \bmod p = 0\)。
我们考虑询问怎么解决。首先有 \({a_l}^{{a_{l+1}}^{{\dots}^{a_r}}} \bmod p\)，我们可以把上面那一大坨先放到扩展欧拉定理里面，递归解决。
我们记录真实值和取模后的值。特殊的，当真实值被设为 \(-1\) 时则代表以及超过模数，使用下面的情况。
首先特判当 \(p=1\) 时可以直接返回 \(0\)（取模后的值）和 \(1\) （真实值）；然后特判 \(a\) 为 \(1\) 的情况，因为当 \(a\) 为 \(1\) 时，当前情况不管 \(p\) 为啥都真实值和取模后的值都为 \(1\)，所以一定是归类在第一种里面。
看到这里我们来证明一下时间复杂度。
我们对 \(\varphi(p)\) 进行讨论：
- 当 \(\varphi(p)\) 为质数时：
- \(p=2,\varphi(p)=1\)，此时下一轮一定会停止递归。
- \(p\ne 2,\varphi(p)=p-1\)，此时下一轮 \(p\)（此时的 \(\varphi(p)\)）一定为偶数。
- 当 \(\varphi(p)\) 不为质数时：
- \(p\) 为偶数时，根据欧拉函数的计算公式，对于 \(p=\prod_{i=1}^{x} {c_i}^{d_i}(c_i>1)\) 有 \(\varphi(p)=p\times \prod_{i=1}^{x}\frac{c_i-1}{c_i}\)，因为 \(p\) 为偶数，即一定有一个 \(c_i=2\)，则 \(p\) 至少会减少 \(\frac12\)。
- \(p\) 为奇数时，根据欧拉函数的计算公式，对于 \(p=\prod_{i=1}^{x} {c_i}^{d_i}(c_i>1)\) 有 \(\varphi(p)=p\times \prod_{i=1}^{x}\frac{c_i-1}{c_i}\)，因为 \(p\) 为奇数且 \(p\) 不为质数，即一定有一个奇数 \(c_i\) 且没有偶数 \(c_i\)，又因为 \(c_i-1\) 一定为偶数，则下一轮 \(p\)（此时的 \(\varphi(p)\)）一定为偶数。
综上，我们证明了两次操作之后，\(p\) 一定会乘上 \(\frac12\)。所以说一次询问的递归层数为 \(O(\log p)\) 层。而快速幂的时间复杂度为 \(O(\log V)\)（\(V\) 为值域），则每次查询时间复杂度为 \(O(\log p\log V)\)。
对于快速求欧拉函数，因为 \(p\in[1,2\times 10^7]\)，我们可以预处理出这个范围里的欧拉函数值。时间复杂度 \(O(n)\)。
时间复杂度：\(O(m\log p\log V)\)。
点击查看代码
#include<bits/stdc++.h>#define int i128
#define pii pair<int,int>
#define pll pair<long long,long long>
#define ll long long
#define i128 __int128#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define in4(a,b,c,d) a=read(), b=read(), c=read(), d=read()
#define fst first
#define scd second
#define dbg puts("IAKIOI")using namespace std;int read() {int x=0,f=1; char c=getchar();for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1); for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }const int mod = 998244353;
pii qpo(int a,int b,int mod,int opt) {a%=mod; pii res={1,opt?1:0};int B=b;if(a>1) while(res.second*a<mod&&B) B--,res.second*=a;if(!B&&opt) {res.first=res.second; return res;}res.second=-1;for(;b;b>>=1,a=(a*a)%mod) if(b&1) res.first=res.first*a%mod; return res;
}
int inv(int a) {return qpo(a,mod-2,mod,1).fst; }#define maxn 500050int n,m,a[maxn];struct Bit {int c[maxn];void add(int x,int val) {for(;x<maxn;x+=lb(x)) c[x]+=val;}int query(int x) {int res=0;for(;x;x-=lb(x)) res+=c[x];return res;}void alr(int l,int r,int val) {add(l,val); add(r+1,-val);}
}Tr;vector<int> pri;
bool pr[20007000];
int phi[20007000];void pre(int n) {phi[1]=1;For(i,2,n) {if(!pr[i]) phi[i]=i-1,pri.push_back(i);for(auto x:pri) {if(i*x>n) break;pr[i*x]=1;if(i%x==0) {phi[i*x]=phi[i]*x; break;}phi[i*x]=phi[i]*phi[x];}}
}pii dfs(int idx,int lim,int p) {
// cout<<(ll)idx<<' '<<(ll)Tr.query(idx)<<' '<<(ll)lim<<' '<<(ll)p<<' '<<(ll)phi[p]<<'\n';if(idx==lim) return {Tr.query(idx)%p,Tr.query(idx)>=p?-1:Tr.query(idx)};if(Tr.query(idx)<=1&&p>1) return {Tr.query(idx),Tr.query(idx)};if(p==1) return {0,-1}; pii nxt=dfs(idx+1,lim,phi[p]);pii res=qpo(Tr.query(idx),(nxt.scd>=p||nxt.scd<0)?((nxt.fst%phi[p])+phi[p]):nxt.fst,p,nxt.scd>=0?1:-1);
// cout<<"idx:"<<(ll)idx<<" res:"<<(ll)res.fst<<'\n';return res;
}void work() {in2(n,m); pre(20000000);For(i,1,n) {in1(a[i]); Tr.add(i,a[i]); Tr.add(i+1,-a[i]);}while(m--) {int opt,l,r,x;in4(opt,l,r,x);if(opt==1) Tr.alr(l,r,x);else {write(dfs(l,r,x).fst); putchar('\n');}}
}signed main() {
// freopen("data.in","r",stdin);
// freopen("myans.out","w",stdout);
// ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);double stt=clock();int _=1;
// _=read();
// cin>>_;For(i,1,_) {work();}cerr<<"\nTotal Time is:"<<(clock()-stt)*1.0/1000<<" second(s)."<<'\n';return 0;
}