[ 扩展欧拉定理 ] Balkan OI 2016 paper

[ 扩展欧拉定理 ] Balkan OI 2016 paper

题目大意：

求 xxx⋯xn321 $x_1^{x_2^{x_3^{cdots x_n}}}$

根据拓展欧拉定理，可以将 1−n $1-n$ 的问题转化成 2−n $2-n$ 的问题。
时间复杂度 O(nlogn) $O(nlog n)$ 。

#include<bits/stdc++.h>
using namespace std;
inline char nc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void Read(int& x){char c=nc();for(;c<'0'||c>'9';c=nc());for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());
}
#define N 1000010
struct Node{int w;bool f;Node(int w=0,bool f=0):w(w),f(f){}
};
int i,j,k,n,m,tot,T,phi[N],p[N],a[N];
bool f;
bool b[N];
inline void Init(){phi[1]=1;for(int i=2;i<=m;i++){if(!b[i]){p[++tot]=i;phi[i]=i-1;}int t;for(int j=1;j<=tot&&(t=p[j]*i)<=m;j++){if(!(i%(p[j]))){b[t]=1;phi[t]=phi[i]*p[j];break;}phi[t]=phi[i]*(p[j]-1);b[t]=1;}}
}
inline Node Pow(int x,int y,int p){Node Ans;Ans.w=1;for(;y;){if(1ll*Ans.w*x>=p)Ans.f=1;if(y&1)Ans.w=1ll*Ans.w*x%p;y>>=1;if(!y)break;if(1ll*x*x>=p)Ans.f=1;x=1ll*x*x%p;}return Ans;
}
inline int Gcd(int x,int y){if(!y)return x;return Gcd(y,x%y);
}
inline Node Solve(int k,int m){if(m==1)return Node(0,1);Node Ans;if(k==n){Ans.w=a[n]%m;Ans.f=(a[n]>=m);return Ans;}Node t=Solve(k+1,phi[m]);if(Gcd(a[k],m)>1&&t.f)return Pow(a[k],phi[m]+t.w,m);return Pow(a[k],t.w,m);
}
int main(){Read(T);Read(m);Init();while(T--){Read(n);for(i=1;i<=n;i++)Read(a[i]);printf("%dn",Solve(1,m).w);}return 0;
}