https://loj.ac/problem/2142

一个数如果要作为指数，那么它不能直接对模数取模，这是常识； 诸如 c c c c . . c^{c^{c^{c..}}} cccc.. 的函数递增飞快，不是高精度可以描述的，这也是常识。 所以，此题要用到很多数论知识。

φ ( n ) \varphi(n) φ(n) 为 [ 1 , n ] [1,n] [1,n] 中与 n n n 互质的正整数个数（包括 1 1 1）。

φ ( n ) = n ∏ p ∣ n ( 1 − 1 p ) \displaystyle \varphi(n)=n\prod_{p|n}(1-{1\over p}) φ(n)=np∣n∏​(1−p1​) 其中 p p p 为 x x x 的质因子。 如何理解这个式子呢？可以粗略这样理解： ( 1 − 1 p ) \displaystyle (1-{1\over p}) (1−p1​) 意思就是筛掉所有能被 p p p 整除的数，当然这种理解方法是错误的，只能算是感性理解，方便记忆。

摘自维基百科：

几条比较重要的性质： 若 gcd ⁡ ( m , n ) = 1 \gcd(m,n)=1 gcd(m,n)=1，有 φ ( m n ) = φ ( m ) φ ( n ) \varphi(mn)=\varphi(m)\varphi(n) φ(mn)=φ(m)φ(n) 令 m = 2 m=2 m=2，不难得出当 n n n 为奇数时， φ ( 2 n ) = φ ( n ) \varphi(2n)=\varphi(n) φ(2n)=φ(n) 另外，对于质数 p p p，有 φ ( p ) = p − 1 \varphi(p)=p-1 φ(p)=p−1

a φ ( n ) ≡ 1 ( m o d n ) a^{\varphi(n)} \equiv 1 \pmod n aφ(n)≡1(modn) 其中 gcd ⁡ ( a , n ) = 1 \gcd(a,n)=1 gcd(a,n)=1 n n n 为质数的情况就是著名的费马小定理。

a b = { a b    b ; φ ( p ) a b m o d    φ ( p ) + φ ( p ) b ≥ φ ( p ) ( m o d p ) a^b=\begin{cases} a^b\quad \quad \quad \quad\quad \quad \ \ b;\varphi(p)\\ a^{b\mod\varphi(p)+\varphi(p)}\quad b\geq \varphi(p) \end{cases}\pmod p ab={ab  b res=res/i*(i-1); while(n%i==0)n/=i; } if(n>1)res=res/n*(n-1); return res; } struct node { int Mi,sum; node operator +(const node &_)const { return (node){min(Mi,_.Mi),(sum+_.sum)%P[0]}; } }nd[N nd[k].Mi=0; nd[k].sum=arr[l]; return; } int mid=(l+r)>>1; build(k if(y>=P[x])y=y%P[x]+P[x]; DOR(i,x,1) { bool flag; y=Pow(y,i-1,flag); if(flag)y+=P[i-1]; } return y%P[0]; } void update(int k,int L,int R,int l,int r) { if(L if(L1; if(R PW[0][0][i]=1,FL[0][0][i]=(1>=P[i]); FOR(j,1,_N) { PW[0][j][i]=PW[0][j-1][i]*c; FL[0][j][i]=FL[0][j-1][i]|(PW[0][j][i]>=P[i]); if(PW[0][j][i]>=P[i])PW[0][j][i]%=P[i]; } PW[1][0][i]=1,FL[1][0][i]=(1>=P[i]); FOR(j,1,_N) { PW[1][j][i]=PW[1][j-1][i]*PW[0][_N][i]; FL[1][j][i]=FL[1][j-1][i]|(PW[1][j][i]>=P[i]); if(PW[1][j][i]>=P[i])PW[1][j][i]%=P[i]; } } } int main() { scanf("%d%d%d%d",&n,&m,&P[tot=0],&c); FOR(i,1,n)scanf("%d",&a[i]); while(P[tot]!=1) { P[tot+1]=phi(P[tot]); tot++; } P[++tot]=1; pre_compute(); build(1,1,n,a); while(m--) { int op,l,r; scanf("%d%d%d",&op,&l,&r); if(op==0)update(1,l,r,1,n); else printf("%d\n",query(1,l,r,1,n)); } return 0; }