欧拉筛（应用）7.2@亿万星辰 洛谷P4139

#include <bits/stdc++.h>
using namespace std;
#define MAXN 10000000
bool f[MAXN+10];
int phi[MAXN+10],pri[MAXN+10],n,cnt;
void Get_phi(){//欧拉筛筛出范围内的所有phi值 
	phi[1]=1;
	for(int i=2;i<=MAXN;i++)
	{
		if(!f[i]){ 
			pri[++cnt]=i;//保存质数 
			phi[i]=i-1;
		}
		for(int j=1;j<=cnt&&i*pri[j]<=MAXN;j++){
			f[i*pri[j]]=1;//标记已筛量 
			if(i%pri[j]==0){
				phi[i*pri[j]]=phi[i]*pri[j];
				break;
			}
			else phi[i*pri[j]]=phi[i]*(pri[j]-1);
		}
	}
}
int qpow(int a,int b,int mod)//快速幂筛选降低mod
{
	int ans=1;
	for(;b;b>>=1){
		if(b&1) ans=(long long)a*ans%mod;
		a=(long long)a*a%mod; 
	}
	return ans;
}
int solve(int mod)//递归降幂 
{
	if(mod==1) return 0;
	else return qpow(2,solve(phi[mod])+phi[mod],mod);
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("4139.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
    Get_phi();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int p;
		scanf("%d",&p);
		printf("%d\n",solve(p));
	}
	return 0;
}