CF906D Power Tower 题解

题意：给定长度为 $n$ 的序列 $a_i$ 和模数 $p$

$Q$ 次询问区间 $[l,r]$ 的 \[ a_l^{ {a_{l+1}^{ {a_{l+2}^{ ^{ {.}^{ {.}^{ {.}^{ {a_{r} } } } } } } } } } } \] $1 \le n \le 10^5,~1 \le p,a_i \le 10^9,~1\le Q \le 10^5$

显然扩展欧拉定理的应用

关于 $O(\varphi^*(n)=1)\approx O(\log n)$ 的证明，可以看这里 link

注：这里的 $O(\varphi^*(n)=1)$ 指最小的 $x$ 使得 $\varphi^{x}(n)=1$

因此对于每个询问，我们直接从左往右跑就好了，递归实现

注意快速幂要满足扩欧的性质哦，不要乱模

时间复杂度 $O(Q \log \max\{a_i\})$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <unordered_map>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e5+15)

int n,m,a[N];
unordered_map<int,int>phi;
int Euler_phi(int n)
{
    int ans=n;
    for(int i=2; i<=n/i; i++)
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}
int qpow(int a,int b,int p)
{
    int ans=1,base=a;
    while(b)
    {
        if(b&1)
        {
            ans=ans*base;
            if(ans>=p) ans=ans%p+p;
        }
        base=base*base;
        if(base>=p) base=base%p+p;
        b>>=1;
    }
    return ans;
}
int solve(int x,int p,int r)
{
    if(p==1||x==r+1) return 1;
    return qpow(a[x],solve(x+1,phi[p],r),p);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);

    read(n);read(m); phi[1]=1;
    for(int now=m; now!=1; now=phi[now])
        phi[now]=Euler_phi(now);
    for(int i=1; i<=n; i++) read(a[i]);
    int Q; read(Q);
    for(int l,r; Q--; )
    {
        read(l); read(r);
        write(solve(l,m,r)%m); pc('\n');
    }
    return 0;
}