結果

問題 No.2193 メガの下１桁
ユーザー 👑 p-adicp-adic
提出日時 2022-08-14 20:33:29
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 6,657 bytes
コンパイル時間 636 ms
コンパイル使用メモリ 74,556 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-06 21:21:41
合計ジャッジ時間 1,635 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 1 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 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 1 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 1 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 1 ms
5,376 KB
testcase_31 AC 1 ms
5,376 KB
testcase_32 AC 2 ms
5,376 KB
testcase_33 AC 2 ms
5,376 KB
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 1 ms
5,376 KB
testcase_36 AC 1 ms
5,376 KB
testcase_37 AC 1 ms
5,376 KB
testcase_38 AC 2 ms
5,376 KB
testcase_39 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <list>
#include <string>
#include <stdio.h>
#include <stdint.h>
using namespace std;

using ll = long long;

ll Solve( ll& M , const ll& D , const ll& N , const ll& B );

int main()
{

  ll M;
  ll D;
  ll N;
  ll B;
  cin >> M;
  cin >> D;
  cin >> N;
  cin >> B;
  Solve( M , D , N , B );
  return 0;

}

void MemorisePrimeFactor( const ll& Base , list<ll>& pfB , list<ll>& peB );
void MemoriseDivisionData( ll& M , list<ll>& prM , const ll& Base , const list<ll>& pfB );
void Triangle( ll& M , list<ll>& prM , const ll& D , const ll& Base , const list<ll>& pfB , const list<ll>& peB , bool& not_overflow );
void TriangleMemorise( ll& M , list<ll>& prM , const ll& D , const ll& Base , const list<ll>& pfB , const list<ll>& peB , bool& not_overflow , const ll& N );

ll Solve( ll& M , const ll& D , const ll& I , const ll& B )
{

  // Bの各素因数ごとにオイラー関数を計算しそれらとBの最小公倍数でBを置き換える、
  // という操作の有限反復によって得られる不動点がBase
  const ll Base =
    B == 2 ? 2 :
    B == 3 ? 6 :
    B == 4 ? 4 :
    B == 5 ? 20 :
    B == 6 ? 6 :
    B == 7 ? 42 :
    B == 8 ? 8 :
    B == 9 ? 18 :
    B == 10 ? 20 :
    B == 11 ? 220 : 0;

  bool not_overflow = M < Base;
  M %= Base;
  list<ll> pfB{};
  list<ll> peB{};
  list<ll> prM{};
  MemorisePrimeFactor( Base , pfB , peB );

  if( I < Base ){

    for( ll n = 0 ; n < I ; n++ ){

      Triangle( M , prM , D , Base , pfB , peB , not_overflow );

    }
    
  } else {

    TriangleMemorise( M , prM , D , Base , pfB , peB , not_overflow , I );

  }

  const ll answer = M % B;

  if( answer == 10 ){
    
    cout << "A" << endl;

  } else {

    cout << answer << endl;

  }
  
  return answer;

}

void MemorisePrimeFactor( const ll& Base , list<ll>& pfB , list<ll>& peB )
{

  constexpr const ll size = 5;
  constexpr const ll prime[size] = { 2 , 3 , 5 , 7 , 11 };

  for( ll i = 0 ; i < size ; i++ ){

    const ll& p = prime[i];
    
    ll power = 1;
    ll j = Base;
    
    while( j != 0 ){

      if( j % p == 0 ){

	power *= p;
	j /= p;
	
      } else {

	j = 0;
	
      }

    }

    if( power != 1 ){

      pfB.push_back( p );
      peB.push_back( power );

    }

  }

  return;

}

void MemoriseDivisionData( ll& M , list<ll>& prM , const ll& Base , const list<ll>& pfB )
{

  prM.clear();
  
  for( auto itr = pfB.begin() , end = pfB.end() ; itr != end ; itr++ ){

    prM.push_back( M % *itr == 0 ? 0 : M );

  }

  return;

}

void ChineseReminderTheorem( ll& M , const list<ll>& prM , const ll& Base , const list<ll>& peB );

void Triangle( ll& M , list<ll>& prM , const ll& D , const ll& Base , const list<ll>& pfB , const list<ll>& peB , bool& not_overflow )
{

  const ll M_shift = ( M + D ) % Base;
  
  if( not_overflow ){

    ll power = 1;
    
    for( ll i = 0 ; i < M ; i++ ){

      power *= M_shift;

      if( not_overflow && power >= Base ){

	not_overflow = false;

      }

      power %= Base;
      
    }

    M = power;
    return;

  }

  ll power = M_shift;
  // exponent == 0にならないようにBase分ずらしておく
  // 互いに素な素数羃での剰余はBase分ずらしても影響を受けない
  // 互いに素でない素数羃での剰余は! not_overflowなので最初から0
  ll exponent = M + Base;
  M = 1;

  while( exponent != 0 ){

    if( exponent % 2 == 1 ){

      M = ( M * power ) % Base;

    }
    
    exponent /= 2;
    power = ( power * power ) % Base;

  }

  MemoriseDivisionData( M , prM , Base , pfB );
  ChineseReminderTheorem( M , prM , Base , peB );
  return;

}

ll SignatureSafeResidue( const ll& M , const ll& Base );

void ChineseReminderTheorem( ll& M , const list<ll>& prM , const ll& Base , const list<ll>& peB )
{

  if ( Base == 2 ){

    auto itr = prM.begin();
    const ll& m0 = *itr;
    M = m0;

  } else if ( Base == 6 ) {

    auto itr = prM.begin();
    const ll& m0 = *itr;
    itr++;
    const ll& m1 = *itr;
    // 1 = 2 * ( -1 ) + 3 * 1;
    M = SignatureSafeResidue( m0 * 3 - m1 * 2 , Base ); 
    
  } else if ( Base == 4 ){

    auto itr = prM.begin();
    const ll& m0 = *itr;
    M = m0;

  } else if ( Base == 20 ){
    
    auto itr = prM.begin();
    const ll& m0 = *itr;
    itr++;
    const ll& m1 = *itr;
    // 1 = 4 * ( -1 ) + 5 * 1;
    M = SignatureSafeResidue( m0 * 5 - m1 * 4 , Base ); 

  } else if ( Base == 42 ){

    auto itr = prM.begin();
    const ll& m0 = *itr;
    itr++;
    const ll& m1 = *itr;
    itr++;
    const ll& m2 = *itr;
    // 1 = 2 * ( -1 ) + 3 * 1;
    M = m0 * 3 - m1 * 2;
    // 1 = 6 * ( -1 ) + 7 * 1;
    M = SignatureSafeResidue( M * 7 - m2 * 6 , Base );
    
  } else if ( Base == 8 ){

    auto itr = prM.begin();
    const ll& m0 = *itr;
    M = m0;

  } else if ( Base == 18 ){
    
    auto itr = prM.begin();
    const ll& m0 = *itr;
    itr++;
    const ll& m1 = *itr;
    // 1 = 2 * ( -4 ) + 9 * 1;
    M = SignatureSafeResidue( m0 * 9 - m1 * 8 , Base ); 

  } else {

    auto itr = prM.begin();
    const ll& m0 = *itr;
    itr++;
    const ll& m1 = *itr;
    itr++;
    const ll& m2 = *itr;
    // 1 = 4 * ( -1 ) + 5 * 1;
    M = m0 * 5 - m1 * 4;
    // 1 = 20 * ( -6 ) + 11 * 11;
    M = SignatureSafeResidue( M * 121 - m2 * 120 , Base );

  }

  return;

}

ll SignatureSafeResidue( const ll& M , const ll& Base )
{

  if( M >= 0 ){

    return M % Base;

  }

  const ll N = ( -M ) % Base;
  return N == 0 ? N : Base - N;
  
}

void TriangleMemorise( ll& M , list<ll>& prM , const ll& D , const ll& Base , const list<ll>& pfB , const list<ll>& peB , bool& not_overflow , const ll& I )
{

  list<ll> answer_memory{};

  for( ll i = 0 ; i <= Base ; i++ ){

    answer_memory.push_back( M );
    Triangle( M , prM , D , Base , pfB , peB , not_overflow );

  }
  
  answer_memory.push_back( M );

  bool not_found = true;
  // 後述する理由でnumの初期化は不要だがコンパイル時に警告が出るので初期化する。
  ll first_occurrence = 0;

  auto itr = answer_memory.begin();

  for( ll i = 0 ; i < Base && not_found ; i++ ){

    if( *itr == M ){

	not_found = false;
	first_occurrence = i;

    } else {

      itr++;

    }

  }

  // [0]から[Base]までにはBase + 1成分あるので、鳩の巣原理からそこに必ずループが含まれる。
  // 従って[Base + 1]は[0]から[Base - 1]までに必ず出現する。
  // すなわちfirst_occurrence < Baseとなり、period > 1となる。
  const ll period = Base + 1 - first_occurrence;
  const ll d = ( I - first_occurrence ) % period;

  for( ll i = 0 ; i < d ; i++ ){

    itr++;

  }
  
  M = *itr;
  return;
  
}
0