题意

求$2^{2^{2...}}\ mod\ p$222... mod p

思路

设$f(p)=2^{2^{2...}}\ mod\ p$f(p)=222... mod p
根据欧拉定理的推论，$a^b\ mod\ p=a^{b\% \varphi(p)+\varphi(p)}\ mod\ p，(b>\varphi(p))$ab mod p=ab%φ(p)+φ(p) mod p，(b>φ(p))
所以$2^{2^{2..}}\ mod\ p=2^{f(\varphi(p))+\varphi(p)}\ mod \ p$222.. mod p=2f(φ(p))+φ(p) mod p
递归即可。

代码

#include<cstdio>

int t, p;
int phi[10000001];

int power(int a, int b, int m) {
	long long res = 1;
	for (; b; b >>= 1) {
		if (b & 1) res = res * a % m; 
		a = (long long)a * a % m;
	}
	return res;
}

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

int main() {
	phi[1] = 1;
	for (int i = 2; i <= 10000000; i++)
		if (!phi[i]) 
			for (int j = i; j <= 10000000; j += i) {
				if (!phi[j]) phi[j] = j;
				phi[j] = phi[j] / i * (i - 1);
			}
	scanf("%d", &t);
	for (; t; t--) {
		scanf("%d", &p);
		printf("%d\n", solve(p));
	}
}