我觉得这题最有意思的其实是 "最终会固定为一个数" 这个结论。
扩展欧拉定理：\(a^b\bmod p\)，当 \(b\ge \varphi(p)\) 时，\(a^b\equiv a^{b\bmod \varphi(p) + \varphi(p)}\pmod p\)。
所以 \(2^{2^{2^{\cdots}}}\) 可以递归求解。边界条件 \(p=1\)。
复杂度如何保证？其实就是算 \(p=\varphi(p)\) 会递归多少次。
发现：若 \(2\mid p\)，至少减半；否则，\(2\mid \varphi(p)\)
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 5;
typedef long long ll;
int T;
int p, phi[N];
bool isp[N] = {};
int cnt = 0, pr[N];
void init() {
memset(isp, true, sizeof isp);
isp[0] = isp[1] = false;
phi[1] = 1;
for (int i = 2; i <= N - 5; i++) {
if (isp[i]) {
pr[++cnt] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= cnt && pr[j] * i <= N - 5; j++) {
isp[pr[j] * i] = false;
if (i % pr[j] == 0) {
phi[pr[j] * i] = phi[i] * pr[j];
break;
}
phi[pr[j] * i] = phi[pr[j]] * phi[i];
}
}
}
ll fpow(ll a, ll b, ll p) {
ll mul = 1;
while (b) {
if (b & 1)
mul = mul * a % p;
a = a * a % p;
b >>= 1;
}
return mul;
}
ll f(ll p) {
if (p == 1)
return 0;
return fpow(2, f(phi[p]) + phi[p], p);
}
void write(__int128 x) {
if (x < 0) {
putchar('-');
write(-x);
return ;
}
if (x < 10) {
putchar((char)(x + '0'));
return ;
}
write(x / 10);
putchar((char)(x % 10 + '0'));
return ;
}
int main() {
init();
cin >> T;
while (T--) {
cin >> p;
// cout << phi[p] << endl;
cout << f(p) << endl;
}
return 0;
}