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

提出ソース

結果

問題	No.181 A↑↑N mod M
ユーザー	👑 p-adic
提出日時	2022-10-31 15:07:38
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	8,391 bytes
コンパイル時間	2,154 ms
コンパイル使用メモリ	212,200 KB
実行使用メモリ	10,268 KB
最終ジャッジ日時	2024-07-08 04:08:31
合計ジャッジ時間	8,896 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

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

テストケース

テストケース表示

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

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

ソースコード

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 RESIDUE( A , P ) ( A >= 0 ? A % P : P - ( - A - 1 ) % P - 1 ) 

#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 ){			\
	if( over ){							\
	  ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO;	\
	} else {							\
	  ANSWER = ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER;		\
	  if( ANSWER > MODULO ){					\
	    over = true;						\
	    ANSWER %= MODULO;						\
	  }								\
	}								\
      }									\
      EXPONENT_FOR_SQUARE_FOR_POWER /= 2;				\
      if( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){				\
	if( over ){							\
	  ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
	} else {							\
	  ARGUMENT_FOR_SQUARE_FOR_POWER = ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER; \
	  if( ARGUMENT_FOR_SQUARE_FOR_POWER > MODULO ){			\
	    over = true;						\
	    ARGUMENT_FOR_SQUARE_FOR_POWER %= MODULO;			\
	  }								\
	}								\
      }									\
    }									\
  }									\



// 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 , vector<uint>& exponent )
{
  uint L = 0;
  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++;
    }
    exponent_copy = exponent;
    if( updating ){
      CarmichaelTransformation( exponent_copy );
    }
  }
  ll square;
  FOR( i , 0 , L ){
    uint& exponent_i = exponent_copy[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;
}

template <typename INT>
INT GCD( const INT& b_0 , const INT& b_1 );

template <typename INT>
INT GCD( const INT& b_0 , const INT& b_1 )
{

  INT b[2] = { b_0 , b_1 };
  int i_0 = ( b_0 >= b_1 ? 0 : 1 );
  int i_1 = 1 - i_0;

  while( b[i_1] != 0 ){

    b[i_0] %= b[i_1];
    swap( i_0 , i_1 );

  }

  return b[i_0];

}

template <typename INT>
INT ChineseReminderTheorem( const INT& b_0 , const INT& c_0 , const INT& b_1 , const INT& c_1 )
{
  
  INT a[2][2];
  INT b[2] = { b_0 , b_1 };
  int i_0 = ( b_0 >= b_1 ? 0 : 1 );
  int i_1 = 1 - i_0;

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

    INT ( & ai )[2] = a[i];

    for( uint j = 0 ; j < 2 ; j++ ){
      ai[j] = ( i == j ? 1 : 0 );
    }

  }
  
  INT q;

  while( b[i_1] != 0 ){

    INT& b_i_0 = b[i_0];
    INT& b_i_1 = b[i_1];
    INT ( &a_i_0 )[2] = a[i_0];
    INT ( &a_i_1 )[2] = a[i_1];
    q = b_i_0 / b_i_1;
    a_i_0[i_0] -= q * a_i_1[i_0];
    a_i_0[i_1] -= q * a_i_1[i_1];
    b_i_0 %= b_i_1;
    swap( i_0 , i_1 );

  }

  INT& gcd = b[i_0];
  INT c = c_0 % gcd;

  if( c_1 % gcd != c ){

    return -1;

  }
  
  INT lcm = ( b_0 / gcd ) * b_1;
  INT ( &a_i_0 )[2] = a[i_0];
  INT& a_i_00 = a_i_0[0];
  a_i_00 *= ( c_1 - c ) / gcd;
  a_i_00 = RESIDUE( a_i_00 , lcm );
  INT& a_i_01 = a_i_0[1];
  a_i_01 *= ( c_0 - c ) / gcd;
  a_i_01 = ( a_i_01 >= 0 ? a_i_01 % lcm : lcm - ( - a_i_01 - 1 ) % lcm - 1 );
  return ( c + a_i_00 * b_0 + a_i_01 * b_1 ) % lcm;

}

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_carmichael = M;
  vector<uint> exponent{};
  LimitCarmichael( M_carmichael , exponent );
  uint exponent_size = exponent.size();
  vector<uint> exponent_A( exponent_size );
  ll A_coprime = A;
  ll M_coprime = M_carmichael;
  FOR( i , 0 , exponent_size ){
    if( exponent[i] != 0 ){
      const uint& P_i = GetPrime( i );
      if( A_coprime % P_i == 0 ){
	uint& exponent_A_i = exponent_A[i];
	while( A_coprime % P_i == 0 ){
	  A_coprime /= P_i;
	  exponent_A_i++;
	}
	while( M_coprime % P_i == 0 ){
	  M_coprime /= P_i;
	}
      }
    }
  }
  ll A_not_coprime = A / A_coprime;
  ll M_not_coprime = M_carmichael / M_coprime;
  ll answer_coprime_factor = 1;
  ll answer_not_coprime_factor = 1;
  bool over = false;
  vector<ll> memory{};
  uint memory_size = 0;
  ll answer = 1;
  FOREQ( i , 1 , N ){
    if( over ){
      POWER( A_power , A , answer , M_coprime );
      answer = ChineseReminderTheorem<ll>( M_not_coprime , 0 , M_coprime , A_power );
      FOR( j , 0 , memory_size ){
	if( memory[j] == answer ){
	  RETURN( memory[ j + ( ( N - j ) % ( memory_size - j ) ) ] % M );
	}
      }
      memory.push_back( answer );
      memory_size++;
    } else {
      POWER( A_coprime_power , A_coprime , answer , M_carmichael );
      answer_coprime_factor = A_coprime_power;
      POWER( A_not_coprime_power , A_not_coprime , answer , M_carmichael );
      answer_not_coprime_factor = A_not_coprime_power;
      if( over ){
	answer = ( answer_not_coprime_factor * answer_coprime_factor ) % M_carmichael;
      } else {
	answer = answer_not_coprime_factor * answer_coprime_factor;
	if( answer >= M_carmichael ){
	  answer %= M_carmichael;
	  over = true;
	}
      }
    }
  }
  RETURN( answer % M );
}

yukicoder

結果

テストケース

ソースコード