bzoj 3884 上帝与集合的正确用法（递归，欧拉函数）

【题目链接】

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

【题意】

求2^2^2… mod p

【思路】

设p=2^k * q+（1/0），使q为一个奇数

　第二项如果是1，mod 1 为0可以忽略。

则我们求：

2^2^2… mod p

=2^k*(2^(2^2…-k) mod q)

因为q是奇数所以与2互质，根据欧拉定理：

a^phi(p) mod p=1,(a,p)=1

转化为：

2^k*(2^(2^2…mod phi(p) – k mod phi(p)))

对于前一项可以递归求解，子问题为solve(phi(p))，递归边界为p=1，此时返回0。

【代码】

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 typedef long long ll;
 7 const int N =  1e5+10;
 8 
 9 ll pow(ll a,ll p,ll mod)
10 {
11     ll ans=1;
12     while(p) 
13     {
14         if(p&1) ans=(ans*a)%mod;
15         a=(a*a)%mod; p>>=1;
16     }
17     return ans;
18 }
19 ll phi(ll x)
20 {
21     ll ans=x;
22     for(int i=2;i*i<=x;i++) if(x%i==0)
23     {
24         ans=ans/i*(i-1);
25         while(x%i==0) x/=i;
26     }
27     if(x>1) ans=ans/x*(x-1);
28     return ans;
29 }
30 
31 int n,T,P;
32 
33 ll solve(ll p)
34 {
35     if(p==1) return 0;
36     int k=0;
37     while(~p&1) p>>=1,k++;
38     ll pi=phi(p);
39     ll ans=solve(pi);
40     ans=(ans+pi-k%pi)%pi;
41     ans=pow(2,ans,p)%p;
42     return ans<<k;
43 }
44 
45 int main()
46 {
47     scanf("%d",&T);
48     while(T--)
49     {
50         scanf("%d",&P);
51         printf("%lld
",solve(P));
52     }
53     return 0;
54 }

P.S.题解抄的PoPoQQQ的，自己又叙述了一遍而已