一道数论题。这很像BZOJ的一道题，好像是P^P^P^P......(无穷多个P)mod M的值。
我们知道当模数P是质数的时候，我们有 X^i=X^(i % p-1) (mod p)
我们不妨对其扩展，得到 X^i=X^(i% φ（p）+ φ（p））（mod p）（i>φ（p））
我们又可证φ（φ（p））<p/2 (从奇偶性进行考虑)
那么我们定义函数sol（i,j,mo）为区间[i,j]在mo下的答案，
我们定义指数上的mod运算 XmodY=（X>Y?X%Y+Y：X）
那么我们有 sol（i，j，mo）=a[i] ^(sol(i+1,j,φ（mo）))//这里的快速幂是在mod意义下的。
我们发现φ（mo）=1时便没有意义做下去了。那么我们一次询问要O（log N*log N）(一个log是给快速幂的)。
#include<bits/stdc++.h> #define MOD(a,b) (a>b?(b)+(a)%(b):(a)) #define sight(c) ('0'<=c&c<='9') #define LL long long #define N 200007 using namespace std; int p[N],fi[N],pim[N>>1],tot,a[N],n,mo,l,r,m; map<int,int> mp; void pri(){ for (int i=2;i<N;i++) { if (!p[i]) fi[i]=i-1,pim[++tot]=i; for (int j=1;j<=tot&&pim[j]*i<N;j++) { p[i*pim[j]]=pim[j]; if (i%pim[j]) fi[i*pim[j]]=fi[i]*(pim[j]-1); else {fi[i*pim[j]]=fi[i]*pim[j]; break;} } } } int P(int k){ int s=k,x=k; if (k<N) return fi[k]; if (mp.count(k)) return mp[k]; for(int i=2;i*i<=k;i++) { if(k%i==0) s=s/i*(i-1); while(k%i==0) k/=i; } if(k>1) s=s/k*(k-1); mp[x]=s; return s; } inline void read(int &x){ static char c; for (c=getchar();!sight(c);c=getchar()); for (x=0;sight(c);c=getchar())x=x*10+c-48; } void write(LL x){if (x<10) {putchar('0'+x); return;} write(x/10); putchar('0'+x%10);} inline void writeln(LL x){ if (x<0) putchar('-'),x*=-1; write(x); putchar(' '); } LL qsm(LL x,LL y,LL mo){ static LL anw; for (anw=1;y;y>>=1,x=MOD(x*x,mo))if (y&1) anw=MOD(anw*x,mo); return anw; } LL sol(int l,int r,int mo){ if (l==r||mo==1) return MOD(a[l],mo); return qsm(a[l],sol(l+1,r,P(mo)),mo); } int main () { freopen("d.in","r",stdin); pri(); read(n); read(mo); for (int i=1;i<=n;i++) read(a[i]); read(m); while (m--) { read(l),read(r); writeln(sol(l,r,mo)%mo); }return 0; }