結果
問題 | No.2193 メガの下1桁 |
ユーザー | 👑 p-adic |
提出日時 | 2022-08-04 09:47:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 6,470 bytes |
コンパイル時間 | 1,039 ms |
コンパイル使用メモリ | 74,512 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-24 15:43:54 |
合計ジャッジ時間 | 1,647 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 1 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | AC | 2 ms
5,248 KB |
testcase_15 | AC | 2 ms
5,248 KB |
testcase_16 | AC | 2 ms
5,248 KB |
testcase_17 | AC | 2 ms
5,248 KB |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 2 ms
5,248 KB |
testcase_21 | AC | 2 ms
5,248 KB |
testcase_22 | AC | 2 ms
5,248 KB |
testcase_23 | AC | 2 ms
5,248 KB |
testcase_24 | AC | 2 ms
5,248 KB |
testcase_25 | AC | 2 ms
5,248 KB |
testcase_26 | AC | 2 ms
5,248 KB |
testcase_27 | AC | 1 ms
5,248 KB |
testcase_28 | AC | 2 ms
5,248 KB |
testcase_29 | AC | 2 ms
5,248 KB |
testcase_30 | AC | 2 ms
5,248 KB |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | AC | 1 ms
5,248 KB |
testcase_34 | AC | 1 ms
5,248 KB |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | AC | 1 ms
5,248 KB |
testcase_39 | WA | - |
ソースコード
#include <iostream>#include <list>#include <vector>#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 , constll& N );ll Solve( ll& M , const ll& D , const ll& N , const ll& B ){// Bの各素因数ごとにオイラー関数を計算しそれらとBの最小公倍数でBを置き換える、// という操作の有限反復によって得られる不動点がBaseconst 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( N < Base ){for( ll n = 0 ; n < N ; n++ ){Triangle( M , prM , D , B , pfB , peB , not_overflow );}} else {TriangleMemorise( M , prM , D , B , pfB , peB , not_overflow , N );}const ll answer = M % B;if( M == 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 ){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;}if( M == 0 ){return;}ll power = M_shift;ll exponent = M;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 == 1 ){M = 0;} else 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 , constll& N ){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 = ( N - first_occurrence ) % period;for( ll i = 0 ; i < d ; i++ ){itr++;}M = *itr;return;}