题解 P4139 【上帝与集合的正确用法】
Siyuan
2019-02-08 11:02:56
[$$\Large\texttt{My Blog}$$](https://hydingsy.github.io/articles/problem-BZOJ-3884-God-and-Set/)
---
## Description
> 题目链接：[Luogu 4139](https://www.luogu.org/problemnew/show/P4139)
求如下式子的值：
$$2^{2^{2\cdots}}\bmod p$$
本题 $T$ 组数据。
数据范围：$1\le T\le 1000$，$1\le p\le 10^7$
------
## Solution
首先我们可以根据**扩展欧拉定理**：
$$\text{当}\ b\ge \varphi(p)\ \text{时，有}\ a^b\equiv a^{b\bmod \varphi(p)+\varphi(p)}\pmod p$$
得到：
$$2^{2^{2\cdots}}\bmod p=2^{(2^{2\cdots}\bmod \varphi(p)+\varphi(p))}\bmod p$$
很显然这是一个递归式子，边界条件为 $p=1$，此时式子的值为 $0$。
对于 $\varphi(p)$，我们可以线性筛预处理。
**时间复杂度**：$O(P+T\log p)$
------
## Code
```cpp
#include <cstdio>
const int N=1e7+5,M=N/10;
int n,tot,p[M],phi[N];
bool flg[N];
void sieve(int n) {
phi[1]=1;
for(int i=2;i<=n;++i) {
if(!flg[i]) p[++tot]=i,phi[i]=i-1;
for(int j=1;j<=tot&&i*p[j]<=n;++j) {
flg[i*p[j]]=1;
if(i%p[j]==0) {
phi[i*p[j]]=phi[i]*p[j];
break;
} else {
phi[i*p[j]]=phi[i]*phi[p[j]];
}
}
}
}
int pow(int x,int p,int mod) {
int ret=1;
for(;p;p>>=1,x=1LL*x*x%mod) if(p&1) ret=1LL*ret*x%mod;
return ret;
}
int solve(int p) {
if(p==1) return 0;
return pow(2,solve(phi[p])+phi[p],p);
}
int main() {
sieve(N-5);
int T;
for(scanf("%d",&T);T--;) {
int p;
scanf("%d",&p);
printf("%d\n",solve(p));
}
return 0;
}
```