Loading... ## 题意 给定一个长度为 $n$ 的数列 $w$ 和模数 $p$，有 $q$ 次询问，每次询问给定 $l,r$，求$w_l^{w_{l+1}^{w_{l+2}^{{\cdots}^{w_r}}}} \bmod p$的值。 $n,q\leq 10^5,p\leq 10^9$ ## 题解 根据扩展欧拉定理： $$ a^b \equiv \begin{cases} a^{b \bmod \varphi(m)}, &\gcd(a,m) = 1, \\ a^b, &\gcd(a,m)\ne 1, b < \varphi(m), \\ a^{(b \bmod \varphi(m)) + \varphi(m)}, &\gcd(a,m)\ne 1, b \ge \varphi(m). \end{cases} \pmod m $$ 那么考虑这个幂塔，就是一直递归计算，那么每次层的模数 $p'$ 都会变成 $\varphi(p')$，可以发现最多递归 $\mathcal{O}(\log p)$ 次。 注意实现细节，要记录质数是否超过 $\varphi(p')$。 ```cpp #include<cstdio> #include<unordered_map> #include<algorithm> // #define ONLINE_JUDGE #define INPUT_DATA_TYPE long long #define OUTPUT_DATA_TYPE long long INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){register char s[20];register int i=0;if(x<0){x=-x;putchar('-');}if(x==0){putchar('0');return;}while(x){s[i++]=x%10;x/=10;}while(i){putchar(s[--i]+'0');}return;} long long w[100010]; std::unordered_map<long long,long long> ump; long long phi(register long long x){ if(ump[x]) return ump[x]; register long long i,res=x; register long long cp=x; for(i=2;i*i<=x;++i) if(x%i==0){ res/=i;res*=(i-1); while(x%i==0) x/=i; } if(x>1) res/=x,res*=(x-1); ump[cp]=res; return res; } long long qpow(register long long base,register long long e,register long long mod){ register long long res=1; while(e){ if(e&1){ res=res*base; if(res>=mod) res=res%mod+mod; } base=base*base; if(base>=mod) base=base%mod+mod; e>>=1; } return res; } long long calc(int l,int r,long long mod){ if(mod==1||l==r+1) return 1; long long t=calc(l+1,r,phi(mod)); return qpow(w[l],t,mod); } int main(){ #ifndef ONLINE_JUDGE freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); #endif register int i,l,r; int n=read(); register long long mod=read(); for(i=1;i<=n;++i) w[i]=read(); int q=read(); for(i=0;i<q;++i){ l=read(); r=read(); print(calc(l,r,mod)%mod);putchar('\n'); } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; } ``` 最后修改：2024 年 04 月 21 日 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏