結果
| 問題 |
No.2193 メガの下１桁
|
| コンテスト | |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2022-08-14 20:33:29 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 23 ms / 2,000 ms |
| コード長 | 6,657 bytes |
| コンパイル時間 | 1,119 ms |
| コンパイル使用メモリ | 73,916 KB |
| 最終ジャッジ日時 | 2025-01-30 22:34:01 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 40 |
ソースコード
#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;
}