Power Tower

CodeForces - 906D

题目大意:有N个数字,然后给你q个区间,要你求每一个区间中所有的数字从左到右依次垒起来的次方的幂对m取模之后的数字是多少。

用到一个新知识,欧拉降幂定理

记住公式 $\LARGE n^x \equiv n^{\varphi(m)\ +\ x\ mod\ \varphi(m)}(mod\ m)​$这个式子当且仅当x>φ(m)时满足。那么就可以递归求解了。

暂时不太明白怎么证明

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#define maxn 100010
#define Mod(a,b) a<b?a:a%b+b
using namespace std;
long long n,m,a[maxn];
map<long long,long long>p;
long long qread(){
long long i=,j=;
char ch=getchar();
while(ch<''||ch>''){if(ch=='-')j=-;ch=getchar();}
while(ch<=''&&ch>='')i=i*+ch-'',ch=getchar();
return i*j;
}
long long Pow(long long x,long long y,long long mod){
long long res=;
while(y){
if(y&)res=Mod(res*x,mod);
x=Mod(x*x,mod);
y>>=;
}
return res;
}
long long phi(long long k){
long long s=k,x=k;
if(p[k])return p[k];
for(long long i=;i*i<=k;i++){
if(k%i==)s=s/i*(i-);
while(k%i==)k/=i;
}
if(k>)s=s/k*(k-);
p[x]=s;return s;
}
long long solve(int l,int r,long long mod){
if(l==r||mod==)return Mod(a[l],mod);
return Pow(a[l],solve(l+,r,phi(mod)),mod);
}
int main(){
freopen("Cola.txt","r",stdin);
n=qread();m=qread();
for(int i=;i<=n;i++)a[i]=qread();
int Q;scanf("%d",&Q);
int l,r;
while(Q--){
scanf("%d%d",&l,&r);
cout<<solve(l,r,m)%m<<endl;
}
return ;
}



05-11 14:59