题意
求
\[2^{2^{2^{\cdots}}} \bmod p \]的值
sol
高次幂算法，使用扩展欧拉定理降幂
\[a^p \equiv a^{p \bmod \phi(m) + \phi(m)}\pmod{m} (b \ge \phi(m)) \]由于当 \(m=1\) 时，无论 \(a^p\) 取何值，结果均为 \(0\) ，因此递归计算即可
\(\phi\) 计算
由算数基本定理，得 $$n=\prod_{i=1}^k a_i^{p_i}$$
则 $$\phi(i) = n\cdot \prod_{i=1}^k \frac{a_i-1}{a_i}$$
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int eular(int x){
int res = x;
for (int i = 2; i <= x / i; i ++ ){
if (x % i == 0){
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
}
if (x > 1) res = res / x * (x - 1);
return res;
}
int qpow(int a, int k, int p){
int ans = 1;
while (k){
if (k & 1) ans = (long long) ans * a % p;
a = (long long) a * a % p;
k >>= 1;
}
return ans;
}
int solve(int p){
if (p <= 2) return 0;
int phi = eular(p);
return qpow(2, phi + solve(phi), p);
}
int main(){
int T;
scanf("%d", &T);
while (T -- ){
int p;
scanf("%d", &p);
printf("%d\n", solve(p));
}
}