一切罪恶的源头 SHOI2017相逢是问候的起源= = 看po姐姐怎么花式虐人，随便想个题让我等蒟蒻跪下膜拜。 http://blog.csdn.net/popoqqq/article/details/43951401
#include<cstdio> #include<algorithm> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=1e6+5; int phi[N],pri[N],tot; typedef long long ll; bool vis[N]; int p,cnt; int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline int Phi(int x) { int i,re=x; for(i=2;i*i<=x;i++) if (x%i==0) { re/=i; re*=i-1; while (x%i==0)x/=i; } if (x^1)re/=x,re*=x-1; return re; } inline int pow(ll a,int b,int p) { ll re=1; while (b) { if(b&1)re=re*a%p; a=a*a%p; b>>=1; } return re; } inline int solve(int p) { if (p==1)return 0; int tmp=0; while (~p&1)p>>=1,++tmp; int phip=Phi(p); int re=solve(phip); re=(re+phip-tmp%phip)%phip; re=pow(2,re,p)%p; return re<<tmp; } int main() { int cas; scanf("%d",&cas); while (cas--) { scanf("%d",&p); printf("%d\n",solve(p)); } }