結果
| 問題 |
No.181 A↑↑N mod M
|
| コンテスト | |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2022-10-31 15:07:38 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,391 bytes |
| コンパイル時間 | 2,217 ms |
| コンパイル使用メモリ | 203,720 KB |
| 最終ジャッジ日時 | 2025-02-08 16:20:53 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 6 |
| other | AC * 35 TLE * 2 |
ソースコード
#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 );
}