BZOJ 3884 上帝与集合的正确用法,风油精滴豆豆的正确用法

题目链接

http://www.lydsy.com/JudgeOnline/problem.php?id=3884

思路

要写这道题，需要用到一个神奇的定理：

axmodm=aϕ(m)+xmodϕ(m)modmaxmodm=aϕ(m)+xmodϕ(m)modm

我们设f(x)=222⋯modxf(x)=222⋯modx，则

f(x)=2f(ϕ(x))+ϕ(x)modxf(x)=2f(ϕ(x))+ϕ(x)modx

这样，我么就可以递归求解f(x)f(x)。

容易证明：f(x)f(x)中xx每次会除以22，因此时间复杂度为O(Tp–√logp)O(Tplog⁡p)。

代码 #include <cstdio>int t,p;inline int phi(int x){ int res=x; for(register int i=2; i*i<=x; ++i) { if(x%i==0) { res=(res/i)*(i-1); while(x%i==0) { x/=i; } } } if(x!=1) { res=(res/x)*(x-1); } return res;}inline int quickpow(int a,int b,int mo){ int res=1; while(b) { if(b&1) { res=(1ll*res*a)%mo; } a=(1ll*a*a)%mo; b>>=1; } return res;}int f(int x){ if(x==1) { return 0; } int ph=phi(x); return quickpow(2,f(ph)+ph,x);}int main(){ scanf("%d",&t); while(t--) { scanf("%d",&p); printf("%dn",f(p)); } return 0;}

转载于:https://www.cnblogs.com/Canopus-wym/p/10376214.html