# HE Fredo and Maths ( Math, Totient function )

Fredo and Maths | Totient Function & Math Practice Problems | HackerEarth

T 筆詢問。問 x^x^x^x^x^x... % M，其中有 K 個 x，為多少。

1 ≤ T ≤ 1e5
1 ≤ M ≤ 1e7
1 ≤ K ≤ 1e18
M < X ≤ 1e8, X is always a prime number

```#pragma GCC target ("avx") // ターゲットの変更 sse4, avx, avx2 など

#include <bits/stdc++.h>
using namespace std;

bool np[ ( int ) 1e7 + 1 ];
int phi[ ( int ) 1e7 + 1 ];

int int_pow( int v, int p, int m ) {
int res = 1;
while( p ) {
if( p & 1 ) {
res = 1LL * res * v % m;
}
p >>= 1;
v = 1LL * v * v % m;
}
return res;
}

int dfs( int x, int k, int m ) {
if( m == 1 ) return 0;
if( k == 1 ) return x % m;
return int_pow( x, dfs( x, k - 1, phi[ m ] ), m );
}

signed main() {
for( int i = 1; i <= ( int ) 1e7; ++i ) {
phi[ i ] = i;
}
for( int i = 2; i <= ( int ) 1e7; ++i ) {
if( np[ i ] ) continue;
for( int j = i; j <= ( int ) 1e7; j += i ) {
if( j != i ) {
np[ j ] = true;
}
phi[ j ] = phi[ j ] / i * ( i - 1 );
}
}
int T;
scanf( "%d", &T );
for( int ti = 0; ti < T; ++ti ) {
int X, M;
long long K;
scanf( "%d %lld %d", &X, &K, &M );
printf( "%d\n", dfs( X, min( 1LL * M, K ), M ) );
}
return 0;
}
```