题意：求$2^{2^{2^{2^{...}}}} \mod p$的值。$p \leq 10^7$
最开始想到的是$x \equiv x^2 \mod p$，然后发现不会做。。。
我们可以想到拓展欧拉定理：$a^b \equiv a^{b \mod \varphi (p) + \varphi (p)} \mod p$，而当$b < p$时有更强的结论$a^b \equiv a^{b \mod \varphi (p)} \mod p$。我们发现利用拓展欧拉定理可以递归下去处理$2^{2^{2^{2^{...}}}} \mod \varphi (p)$的问题，直到$\varphi (p)$为$1$时得到答案$0$。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
;
;
char c = getchar();
while(!isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
] , cntPrime;
];
inline int ola(int x){
int sum = x;
; i * i <= x && i <= cntPrime ; i++)
){
)
x /= prime[i];
sum = sum / prime[i] * (prime[i] - );
}
)
sum = sum / x * (x - );
return sum;
}
inline int poww(long long a , long long b , int mod){
;
while(b){
)
times = times * a % mod;
a = a * a % mod;
b >>= ;
}
return times;
}
long long dfs(int x){
)
;
, ola(x) + dfs(ola(x)) , x);
}
int main(){
; i <= ; i++)
if(!isprime[i]){
prime[++cntPrime] = i;
; j++)
isprime[j * i] = ;
}
for(int T = read() ; T ; T--){
int a = read();
cout << dfs(a) << endl;
}
;
}