#812894 (C++17) No.181 A↑↑N mod M

提出ソース

結果

問題	No.181 A↑↑N mod M
ユーザー	👑 p-adic
提出日時	2022-10-31 12:40:13
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	5,014 bytes
コンパイル時間	2,229 ms
コンパイル使用メモリ	208,976 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-08 02:07:45
合計ジャッジ時間	3,217 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	1 ms 6,944 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	1 ms 6,944 KB
testcase_06	AC	1 ms 6,944 KB
testcase_07	WA	-
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	1 ms 6,944 KB
testcase_10	AC	1 ms 6,940 KB
testcase_11	AC	1 ms 6,940 KB
testcase_12	AC	1 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	1 ms 6,940 KB
testcase_16	WA	-
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	1 ms 6,940 KB
testcase_19	AC	1 ms 6,944 KB
testcase_20	AC	1 ms 6,940 KB
testcase_21	AC	1 ms 6,944 KB
testcase_22	AC	1 ms 6,940 KB
testcase_23	WA	-
testcase_24	AC	1 ms 6,940 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	WA	-
testcase_27	AC	2 ms 6,940 KB
testcase_28	AC	1 ms 6,944 KB
testcase_29	AC	1 ms 6,940 KB
testcase_30	AC	2 ms 6,940 KB
testcase_31	AC	1 ms 6,944 KB
testcase_32	AC	2 ms 6,944 KB
testcase_33	AC	2 ms 6,940 KB
testcase_34	AC	1 ms 6,944 KB
testcase_35	AC	1 ms 6,944 KB
testcase_36	AC	2 ms 6,944 KB
testcase_37	AC	1 ms 6,944 KB
testcase_38	AC	1 ms 6,944 KB
testcase_39	AC	1 ms 6,940 KB
testcase_40	AC	2 ms 6,940 KB
testcase_41	AC	2 ms 6,940 KB
testcase_42	AC	1 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード