自动搬运

查看原文

来自洛谷，原作者为

	panda_2134 菜狗

搬运于2025-08-24 21:56:54，当前版本为作者最后更新于2018-01-28 10:42:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

各位dalao应该都知道扩展欧拉定理吧……

大概长这样：

对于任意$b \geq \varphi(p)$,有：

当$b < \varphi(p)$时有$a^b \equiv a^{b \text{ mod } \varphi(p)} (\text{mod } p)$

其中$a,p$可以不互质。

有了这个式子，题目中的$2^{2^{2^{2^{\cdots}}}} \text { mod } p$就很好求了，照着上面的式子递归就行。这里要注意应用条件：这里的指数$b=2^{2^{2^{2^{\cdots}}}}$是满足$b \geq \varphi(p)$的，于是可以直接用第一个式子。

附上代码。本蒟蒻不会线性筛，只好用Eratosthenes筛代替了= =

#include <bits/stdc++.h>
using namespace std;
const int MAXP = 1e7;

int T, p, phi[MAXP+10];

void InitPhi() {
    phi[1] = 1; 
    for(int i=2; i<=MAXP; i++)
        if(!phi[i]) {
            for(int j=i; j<=MAXP; j+=i) {
                if(!phi[j]) phi[j] = j; 
                phi[j] = phi[j] / i * (i-1);
            }
        }
}

inline int fastmul(int a, int x, int mod) {
    int ret = 0;
    while(x) {
        if(x&1) ret = ((ret%mod) + (a%mod))%mod;
        x>>=1; a = ((a%mod) + (a%mod)) %mod;
    }
    return ret;
}

inline int fastpow(int a, int x, int mod) {
    int ret = 1;
    while(x) {
        if(x&1) ret = fastmul(ret, a, mod) % mod;
        x>>=1; a = fastmul(a, a, mod) % mod;
    }
    return ret;
}

int solve(int mod) {
    if(mod == 1) return 0;
    return fastpow(2, solve(phi[mod])+phi[mod], mod);
}

int main() {
    InitPhi();
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &p);
        printf("%d\n", solve(p));
    }
}