题目描述
给定P，求
\[2^{2^{2^{...}}} \% P \]Sol
欧拉函数的运用。
\[a^b \equiv a^{b\%\phi(P)+\phi(P)} (mod P),b>=\phi(P) \]核心操作：一个线性筛处理\(\phi\)，一个递归，一个快速幂。
Code
#include<bits/stdc++.h>
#define N (10000010)
#define V (10000000)
#define ll long long
using namespace std;
int T,tot,p[N],phi[N];
bool used[N];
inline int read(){
int w=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9'){
w=(w<<3)+(w<<1)+(ch^48);
ch=getchar();
}
return w;
}
inline void oula(){
phi[1]=1;
for(int i=2;i<=V;i++){
if(!used[i]) p[++tot]=i,phi[i]=i-1;
for(int j=1;j<=tot&&i*p[j]<=V;j++){
used[i*p[j]]=1;
if(!(i%p[j])){
phi[i*p[j]]=phi[i]*p[j];
break;
}
else phi[i*p[j]]=phi[i]*phi[p[j]];
}
}
return;
}
inline ll ksm(ll a,ll b,ll p){
ll res=1;
while(b){
if(b&1) res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
inline int solve(int k){
if(k==1) return 0;//任何正整数模一都为0
return ksm(2,phi[k]+solve(phi[k]),k);
}
signed main(){
oula();
T=read();
while(T--) printf("%d\n",solve(read()));
return 0;
}