bzoj3884 上帝与集合的正确用法

我们想知道 (2^{2^{2^cdots}}mod p)。
考虑用扩展欧拉定理降幂，

[2^{2^{2^cdots}}equiv 2^{(2^{2^cdots}mod varphi(p))+varphi(p)}mod p. ]

于是定义(f(p)=2^{2^{2^cdots}}mod p)。
则

[f(p)equiv 2^{f(varphi(p))+varphi(p)} mod p. ]

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll T, p;
ll getPhi(ll x){
	ll ans=x;
	for(int i=2; i*i<=x; i++)
		if(x%i==0){
			ans -= ans / i;
			while(x%i==0)	x /= i;
		}
	if(x>1)	ans -= ans / x;
	return ans;
}
ll ksm(ll a, ll b, ll c){
	ll re=1;
	while(b){
		if(b&1)	re = (re * a) % c;
		a = (a * a) % c;
		b >>= 1;
	}
	return re;
}
ll f(ll x){
	if(x==1)	return 0;
	ll phi=getPhi(x);
	return ksm(2, f(phi)+phi, x);
}
int main(){
	cin>>T;
	while(T--){
		scanf("%lld", &p);
		printf("%lld
", f(p));
	}
	return 0;
}