0w1

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

解法:
利用尤拉定理可以知道,x^phi( M ) % M == 1,利用這件事遞迴求解。
因此遞迴的深度不會超過 phi 的數量,使得 phi( phi( phi( ... phi( M ) ... ) = 1。
因為 phi 函數很快收斂,所以 ok ( 吧 )。
不知道為什麼被微卡常數,怒開 avx 優化就過了。

時間 / 空間複雜度:
玄學。

#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;
}