题解 P4139 【上帝与集合的正确用法】

前置之士：欧拉定理和拓展欧拉定理: $a^b\equiv a^{b\ mod\ φ (m)} \ \ \ \qquad\qquad gcd(a,m)=1$ $a^b\equiv a^b \qquad\qquad\qquad\qquad gcd(a,m)\neq 1,b<φ (m)$ $a^b\equiv a^{(b\ mod\ φ (m))+φ (m)} \qquad gcd(a,m)\neq 1,b\ge φ (m)$ 然后我们发现，$p$是随即数据，不把保证$p,a$互质，所以我们用上述后两个结论，也就是拓展欧拉定理。 于是我们可以递归执行，直到模数为0，返回1即可 但是我们发现随着递归的深入，我们的模数也在变，所以我们要预处理出所有的$φ$值，我们可以用线性筛（主要是Eratosthenes筛法TLE了）来预处理 代码如下： ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define debug printf("Now is Line : %d\n",__LINE__) #define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout) #define ll long long il int read() { re int x=0,f=1;re char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') x=x*10+c-48,c=getchar(); return x*f; } #define maxn 10000000 int n,m,f[maxn+5],p[5000000],tot; bool is[maxn+5]; il ll quickpow(ll a,int b,int mod) { ll r=1; while(b) { if(b&1) r=(r*a)%mod; b>>=1; a=(a*a)%mod; } return r; } il ll solve(int mod) { if(mod==1) return 0; return quickpow(2,solve(f[mod])+f[mod],mod); } signed main() { f[1]=1; for(re int i=2;i<=maxn;++i) { if(!is[i]) p[++tot]=i,f[i]=i-1; for(re int j=1;j<=tot;++j) { if(i*p[j]>maxn) break; is[i*p[j]]=1; if(i%p[j]) f[i*p[j]]=f[i]*(p[j]-1); else {f[i*p[j]]=f[i]*p[j];break;} } } int T=read(); while(T--) { n=read(); printf("%lld\n",solve(n)); } return 0; } ```