$$\Large\texttt{My Blog}$$


Description

题目链接:Luogu 4139

求如下式子的值: $$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

#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;
}