题目
给定一个数列，有\(m\)组询问
定义
\[\large f(x-1)={a_x}^{f(x)}
\]
若 \(f(r)=a_r\) 求 \(f(l)\)
对固定的 \(mod\) 取模
分析
根据扩展欧拉定理
\[\large
\begin{cases}
a^x\equiv a^{x\bmod \varphi(p)+\varphi(p)}\pmod p,x\geq \varphi(p)\a^x,otherwise
\end{cases}
\]
一次\(\varphi(p)\)至少会将下一层的模数缩小一半（\(p>2\)）
那么最多\(\log p\)次就会结束递归，那么时间复杂度为\(O(m\log mod)\)
注意一旦\(x\geq \varphi(p)\)一定要补上\(a^{\varphi(p)}\)才能保证正确性
代码
#include <cstdio>
#include <cctype>
#include <map>
#define rr register
using namespace std;
int n,mod,l,r,a[100011];
map<int,int>phi;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
inline signed min(int a,int b){return a<b?a:b;}
inline void Get_Phi(int &p){
rr int now=p,m=p;
for (rr int i=2;i*i<=p;++i)
if (p%i==0){
now=now/i*(i-1);
while (p%i==0) p/=i;
}
if (p>1) now=now/p*(p-1);
p=phi[m]=now;
}
inline signed ksm(int x,int y,int p){
rr long long ans=1,t;
for (;y;y>>=1){
if (y&1){
t=ans*x;
if (t>=p) t=t%p+p;
ans=t;
}
t=1ll*x*x;
if (t>=p) t=t%p+p;
x=t;
}
return ans;
}
inline signed answ(int x,int p){
if (x==r+1||p==1) return 1;
rr int mi=answ(x+1,phi[p]);
return ksm(a[x],mi,p);
}
signed main(){
n=iut(),mod=iut();
for (rr int t=mod;t>1;Get_Phi(t));
for (rr int i=1;i<=n;++i) a[i]=iut();
for (rr int Q=iut();Q;--Q)
l=iut(),r=iut(),print(answ(l,mod)%mod),putchar(10);
return 0;
}