結果

問題 No.181 A↑↑N mod M
コンテスト
ユーザー 👑 p-adic
提出日時 2022-10-31 12:40:13
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,014 bytes
コンパイル時間 2,275 ms
コンパイル使用メモリ 203,048 KB
最終ジャッジ日時 2025-02-08 16:18:02
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 33 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using uint = unsigned int;
using ll = long long;

#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) 
#define CIN( LL , A ) LL A; cin >> A 
#define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX ) 
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) 
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )  
#define QUIT return 0 
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT 

#define POWER( ANSWER , ARGUMENT , EXPONENT , MODULO )			\
  TYPE_OF( ARGUMENT ) ANSWER = 1;					\
  {									\
    TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT );	\
    TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT );	\
    while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){			\
      if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){			\
	ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO;	\
      }									\
      ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
      EXPONENT_FOR_SQUARE_FOR_POWER /= 2;				\
    }									\
  }									\



// 1+i番目の素数を返す
const uint& GetPrime( const uint& i ) noexcept;

const uint& GetPrime( const uint& i ) noexcept
{

  static vector<uint> P{ 2 , 3 , 5 , 7 , 11 };

  uint L = P.size();

  while( i >= L ){

    uint p = P.back() + 2;

    bool prime = false;

    while( ! prime ){

      prime = true;
    
      for( uint j = 0 ; j < L && prime ; j++ ){

	uint& Pj = P[j];
	prime = ( p % Pj != 0 );

	if( Pj * Pj >= p ){

	  j = L;
	
	}

      }

      if( ! prime ){

	p += 2;

      }

    }

    P.push_back( p );
    L++;

  }

  return P[i];

}

void CarmichaelTransformation( vector<uint>& exponent );

void CarmichaelTransformation( vector<uint>& exponent )
{

  uint size = exponent.size();
  vector<uint> exponent_answer( size );
  
  for( uint i = 0 ; i < size ; i++ ){

    uint& exponent_i = exponent[i];

    if( exponent_i != 0 ){

      exponent_i--;
      const uint& P_i = GetPrime( i );
      uint& exponent_answer_i = exponent_answer[i];

      if( exponent_answer_i < exponent_i ){

	exponent_answer_i = exponent_i;

      }

      uint new_factor = P_i - 1;

      for( uint j = 0 ; j < i ; j++ ){

	const uint& P_j = GetPrime( j );

	if( new_factor % P_j == 0 ){

	  new_factor /= P_j;
	  uint new_exponent = 1;

	  while( new_factor % P_j == 0 ){

	    new_factor /= P_j;
	    new_exponent++;

	  }

	  uint& exponent_answer_j = exponent_answer[j];

	  if( exponent_answer_j < new_exponent ){
	  
	    exponent_answer_j = new_exponent;

	  }

	}

	if( new_factor == 1 ){

	  break;
	
	}

      }

    }
   
  }

  exponent = move( exponent_answer );  
  return;

}

void LimitCarmichael( ll& m )
{
  uint L = 0;
  vector<uint> exponent{};
  while( m != 1 ){
    const uint& P_i = GetPrime( L );
    if( m % P_i == 0 ){
      m /= P_i;
      exponent.push_back( 1 );
      uint& exponent_i = exponent.back();
      while( m % P_i == 0 ){
	m /= P_i;
	exponent_i++;
      }
    } else {
      exponent.push_back( 0 );
    }
    L++;
  }
  vector<uint> exponent_copy = exponent;
  CarmichaelTransformation( exponent_copy );
  bool updating = true;
  while( updating ){
    updating = false;
    uint i = 0;
    while( i < L ){
      uint& exponent_i = exponent[i];
      uint& exponent_copy_i = exponent_copy[i];
      if( exponent_i < exponent_copy_i ){
	exponent_i = exponent_copy_i;
	updating = true;
	i++;
	break;
      }
      i++;
    }
    while( i < L ){
      uint& exponent_i = exponent[i];
      uint& exponent_copy_i = exponent_copy[i];
      if( exponent_i < exponent_copy_i ){
	exponent_i = exponent_copy_i;
	updating = true;
      }
      i++;
    }
    if( updating ){
      exponent_copy = exponent;
      CarmichaelTransformation( exponent_copy );
    }
  }
  ll square;
  FOR( i , 0 , L ){
    uint& exponent_i = exponent[i];
    if( exponent_i != 0 ){
      const uint& P_i = GetPrime( i );
      square = P_i;
      while( exponent_i != 0 ){
	if( exponent_i % 2 == 1 ){
	  m *= square;
	}
	square = square * square;
	exponent_i /= 2 ;
      }
    }
  }
  return;
}

int main()
{
  UNTIE;
  constexpr const ll bound = 1000000000;
  CIN_ASSERT( A , 1 , bound );
  CIN_ASSERT( N , 0 , bound );
  constexpr const ll bound_M = 2000;
  CIN_ASSERT( M , 1 , bound_M );
  ll M_copy = M;
  LimitCarmichael( M_copy );
  ll answer = 1;
  vector<ll> memory{};
  memory.push_back( answer );
  FOREQ( i , 1 , N ){
    POWER( tetration , A , answer , M_copy );
    FOR( j , 0 , i ){
      if( memory[j] == tetration ){
	RETURN( memory[ j + ( ( N - j ) % ( i - j ) ) ] % M );
      }
    }
    answer = tetration;
    memory.push_back( tetration );
  }
  RETURN( answer % M );
}
0