扩展欧拉函数：
然后线性筛求欧拉函数。
#include<bits/stdc++.h> using namespace std; const int N = 1e7+10; int cnt,phi[N],p[N/10]; bool vis[N]; void Get_phi(int n){ phi[1] = 1; for (int i = 2; i < n; ++i){ if (!vis[i]) p[cnt++] = i, phi[i] = i-1; for (int j = 0; j < cnt && 1ll*i * p[j] < n; ++j){ vis[i*p[j]] = 1; if (i % p[j] == 0){ phi[i*p[j]] = phi[i] * p[j]; break; } else{ phi[i*p[j]] = phi[i] * phi[p[j]]; } } } } int pow(int x, int p, int mod){ int ret = 1; for (; p; p>>=1,x = 1ll*x*x % mod) if (p & 1) ret = 1ll*ret*x% mod; return ret; } int solve(int p){ if (p == 1) return 0; return pow(2,solve(phi[p])+phi[p],p); } int main(){ Get_phi(N-5); int _; scanf("%d",&_); while(_--){ int p; scanf("%d",&p); printf("%d\n",solve(p)); } return 0; }
