题意
求：
\[2^{2^{2^{\ldots}}} \mod p \]可以证明这个式子一定为一个常数。
\(1 \leq p \leq 10^7\)
思路
根据扩展欧拉定理，可以得到：
\[2^{2^{2^{\ldots}}} \equiv 2^{(2^{2^{\ldots}} \mod \varphi(p)+\varphi(p))}\pmod p \]这个式子可以递归下去，边界条件自然就是 \(p=1\) 的情况，而欧拉函数可以在线性筛的同时 \(O(n)\) 预处理得到。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e7+10;
int prime[N],tot,phi[N];bool vis[N];
void init()
{
for(int i=2;i<N;i++)
{
if(!vis[i]) prime[++tot]=i,phi[i]=i-1;
for(int j=1;j<=tot&&prime[j]*i<N;j++)
{
vis[prime[j]*i]=true;
if(i%prime[j]==0) {vis[prime[j]*i]=true,phi[prime[j]*i]=phi[i]*prime[j];break;}
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
int mul(int a,int b,int p){int res=1;while(b) ((b&1)&&(res=1ll*res*a%p)),a=1ll*a*a%p,b>>=1;return res;}
int solve(int p)
{
if(p==1) return 0;
return mul(2,solve(phi[p])+phi[p],p);
}
int main()
{
init();int T,p;scanf("%d",&T);while(T--) scanf("%d",&p),printf("%d\n",solve(p));
return 0;
}