上帝与集合的正确用法 (欧拉函数，快速幂）HQG

函数，快速幂）HQG"/>

上帝与集合的正确用法 (欧拉函数，快速幂）HQG

这个欧拉函数裸题

先用筛法（埃氏筛还是欧拉筛都可以，反正我用了欧拉筛，因为快）

然后运用欧拉函数积性的性质，solve就可以了，至于求解，快速幂帮您搞定

#include <bits/stdc++.h>
using namespace std ;const int N = 10000010 ;int phi[N],p[N] ;
bool flag[N] ;
int T,n,tot ;void init(int n) {phi[1]=1;for (int i=2;i<=n;i++){if (!flag[i]){p[tot++]=i;phi[i]=i-1;}for (int j=0;j<tot;j++) {if (i*p[j]>n) break;flag[i*p[j]]=true;if (i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}phi[i*p[j]]=phi[i]*(p[j]-1);}}
}
inline int ksmmul(int a,int x,int mod){int t=0 ;while (x){if (x&1) t=(t%mod+a%mod)%mod ;x>>=1 ;a=(a%mod+a%mod)%mod ;}return t ;
}inline int ksmpow(int a,int x,int mod){int t=1 ;while (x){if (x&1) t=ksmmul(t,a,mod)%mod ;x>>=1;a=ksmmul(a,a,mod)%mod ;}return t ;
}
inline int solve(int x){if (x==1) return 0 ;return ksmpow(2,solve(phi[x])+phi[x],x) ;
} 
int main(){init(N) ;scanf("%d",&T) ;while(T--){scanf("%d",&n) ;printf("%d\n",solve(n)) ;}
}