CF906D Power Tower

知识点：拓展欧拉定理、记忆化、欧拉函数、快速幂

题目链接

题意

给定序列$a_i$，$q$次询问$a_{[l,r]}$的数构成以下形式对$m$取模后的结果：
$a_l^{(a_{l+1}^{(a_{i+2}^{(..{.}^{a_{r-1}^{a_r}})})})}$

思路

拓展欧拉定理：
$a^c\equiv a^{c\%\phi (m)+\phi (m)}ifc\ge \phi (m)$
$a^c\equiv a^{c}ifc<\phi (m)$
$(modm)$
其中$\phi (m)$为欧拉函数
令所求形式为：$f(l,r)$
递推式：$f(l,r)=a_l^{f(l+1,r)}$
取模：$f(l,r)\%m=(a_l\%m{)}^{f(l+1,r)\%\phi (m)+\phi (m)}\%m$（假定$c\ge \phi (m)$）
观察到递推式中模数由$m$降为$\phi (m)$、再降为$\phi (\phi (m))等$，证明$\phi (m)$降为$1$的时间复杂度为$O(logm)$：
$m$为偶数：
$m=2^n\times p_i^{n_i}$
$\phi (m)=(2-1)2^{n-1}\times (p_i-1)p_i^{n_i-1}$（因子减少$2$，得证）
$m$为奇数：
$m=p_i^{n_i}$（$p_i$全为奇数）
$\phi (m)=(p_i-1)p_i^{n_i-1}$（p_i-1为偶数，转换为第一种情况，得证）
$\phi (m)$的复合函数预处理一下即可
（未完）

代码

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
using namespace std;
const ll N=1e5+10;

ll n,m;
ll arr[N];
ll q;
map<ll,ll> phi;

inline ll getphi(ll x) {
   
   if(phi[x])
      return phi[x];
   ll t=x;
   ll ans=1;
   for(ll i=2; i*i<=x; i++) {
   
      if(x%i==0) {
   
         ans*=i-1;
         x/=i;
         while(x%i==0) {
   
            ans*=i;
            x/=i;
         }
      }
   }
   if(x!=1)
      ans*=x-1;
   return phi[t]=ans;
}

inline ll exeuler(ll x,ll mod) {
   
   if(x<mod)
      return x;
   return x%mod+mod;
}

inline ll pow(ll a,ll x,ll mod) {
   
   ll ans=1;
   while(x) {
   
      if(x&1)
         ans=exeuler(ans*a,mod);
      a=exeuler(a*a,mod);
      x>>=1;
   }
   return ans;
}

inline ll query(ll l,ll r,ll mod) {
   
   if(l==r)
      return exeuler(arr[l],mod);
   if(mod==1)
      return 1;
   return pow(arr[l],query(l+1,r,getphi(mod)),mod);
}

void solve() {
   
   scanf("%lld%lld",&n,&m);
   for(ll i=1; i<=n; i++)
      scanf("%lld",&arr[i]);
   scanf("%lld",&q);
   while(q--) {
   
      ll l,r;
      scanf("%lld%lld",&l,&r);
      printf("%lld\n",query(l,r,m)%m);
   }
}

int main() {
   
   solve();
   return 0;
}