# 【bzoj3884】上帝与集合的正确用法 扩展欧拉定理

xiaoxiao2021-02-28  39

Description

T行，每行一个正整数，为答案对p取模后的值 Sample Input

3

2

3

6 Sample Output

0

1

4 HINT

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #define ll long long using namespace std; inline 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; } const int N=10000002; int phi[N],flag[N],p[N],tot,P; void pre() { phi[1]=1; for (int i=2;i<N;i++) { if (!flag[i]) p[++tot]=i,phi[i]=i-1; for (int j=1;j<=tot&&i*p[j]<N;j++) { flag[i*p[j]]=1; if (i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;} phi[i*p[j]]=phi[i]*phi[p[j]]; } } } int power(int x,int y,int p) { int ans=1; while (y) { if (y&1) ans=(ll)ans*x%p; y>>=1;x=(ll)x*x%p; } return ans; } int F(int p) { if (p==1) return 0; return power(2,F(phi[p])+phi[p],p); } inline void solve() { P=read(); printf("%d\n",F(P)); } int main() { pre(); int Case=read(); while (Case--) solve(); return 0; }