洛谷4139 bzoj 3884 上帝与集合的正确用法

•题意

求$2^{2^{2^{2^{2^{2^{...^{2}}}}}}}$ (无穷个2) 对p取模的值

•思路

设答案为f(p)

$2^{2^{2^{2^{2^{2^{...^{2}}}}}}}\%p$

$=2^{(2^{2^{2^{2^{2^{...^{2}}}}}}\%varphi(p)+ varphi(p))}\%p$

$=2^{(2^{2^{2^{2^{2^{...^{2}}}}}}\%varphi(p)+ varphi(p))}\%p$

$=2^{(2^{(2^{2^{2^{2^{...^{2}}}}}\%varphi(varphi(p)+varphi(varphi(p))))}\%varphi(p)+ varphi(p))}\%p$

...

得到递推式 $2^{f(varphi(p))+varphi(p)}(mod p)$

利用欧拉降幂

$a^{b}=egin{cases}a^{b\%varphi(p)} gcd(a,p)=1 \ a^{b} gcd(a,p) eq 1,b leqslant varphi(p)\a^{b\%varphi(p)+varphi(p)} gcd(a,p) eq1,bgeqslant varphi(p) \ end{cases}$

由于2的幂数是无穷的，肯定$>p$,所以可以直接使用$a^{b\%varphi(p)+varphi(p)} $

•代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 ll qpow(ll a,ll b,ll mod)
 5 {
 6     ll res=1;
 7     while(b)
 8     {
 9         if(b&1)
10             res=res*a%mod;
11         a=a*a%mod;
12         b>>=1;
13     }
14     return res;
15 }
16 
17 ll phi(ll x)
18 {
19     ll res=x;
20     for(int i=2;i*i<=x;i++)
21     {
22         if(x%i==0)
23         {
24             while(x%i==0)
25                 x/=i;
26             res=res-res/i;
27         }
28     }
29     if(x>1)
30         res=res-res/x;
31     return res;
32 }
33 
34 ll solve(ll m)
35 {
36     if(m==1)
37         return 0;
38 
39     ll p=phi(m);
40     return qpow(2,solve(p)+p,m);
41 }
42 
43 int main()
44 {
45     int t;
46     cin>>t;
47     while(t--)
48     {
49         ll m;
50         cin>>m;
51         cout<<solve(m)<<endl;
52     }
53 }

View Code