CF906D Power Tower

题目大意：给出一段长为 \(n\) 的序列 \(a_1,a_2,\cdots,a_n\)
，一个模数 \(m\) .每次询问给定 \(l,r\)

求 \(a_l^{{a_{l+1}^\cdots}^{a_r}} mod\) \(m\)

思路：不断欧拉降幂即可，\(\log m\)次就可以达到1，由于套了一个快速幂，复杂度 \(O(\log ^2 n)\)。注意取模时应满足广义欧拉定理 在这里卡了好久

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=50005;
int a[N],m,l,r,n,q;
unordered_map<int,int>mp;
int phi(int x)
{
    int tmp=x;
    if(mp.count(x))return mp[x];
    int res=x;
    for(int i=2;i*i<=x;++i)
    {
        if(x%i==0)
        {
            res=res-res/i;
            while(x%i==0)x/=i;
        }
    }
    if(x>1)res=res-res/x;
    return mp[tmp]=res;
}
int mod(int x,int m)
{
    return x>=m?x%m+m:x;
}
int qpow(int n,int k,int p)
{
    int base=n,res=1;
    while(k)
    {
        if(k&1)res=mod(res*base,p);
        base=mod(base*base,p);
        k>>=1;
    }
    return res;
}
int f(int l,int r,int m)
{
    if(l==r||m==1)return mod(a[r],m);
    return qpow(a[l],f(l+1,r,phi(m)),m);
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
    scanf("%lld",&q);
    while(q--)
    {
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",f(l,r,m)%m);
    } 
    return 0;
}

CF906D Power Tower

原文：https://www.cnblogs.com/zzctommy/p/12317327.html