結果

問題 No.2193 メガの下1桁
ユーザー 👑 p-adicp-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 -
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 , const
    ll& N );
ll Solve( ll& M , const ll& D , const ll& N , const ll& B )
{
// BBB
// 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( 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 , const
    ll& 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 < Baseperiod > 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0