結果

問題 No.2193 メガの下1桁
ユーザー SSRS
提出日時 2023-01-13 22:34:09
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,792 bytes
コンパイル時間 2,175 ms
コンパイル使用メモリ 180,524 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-24 18:20:25
合計ジャッジ時間 3,502 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 35 WA * 5
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
const array<int, 11> MODS = {3960, 960, 256, 128, 64, 32, 16, 8, 4, 2, 1};
int modulo(int a, int m){
if (a < m){
return a;
} else {
return a % m + m;
}
}
int modpow(int a, int b, int m){
int ans = 1;
while (b > 0){
if (b % 2 == 1){
ans = modulo(ans * a, m);
ans %= m;
}
a = modulo(a * a, m);
b /= 2;
}
return ans;
}
array<int, 11> modpow(array<int, 11> a, array<int, 11> b){
array<int, 11> c;
for (int i = 0; i < 10; i++){
c[i] = modpow(a[i], b[i + 1], MODS[i]);
}
if (a[0] == 0 && b[0] > 0){
c[10] = 0;
} else {
c[10] = 1;
}
return c;
}
array<int, 11> get(long long x){
array<int, 11> A;
for (int i = 0; i < 11; i++){
A[i] = modulo(x, MODS[i]);
}
return A;
}
array<int, 11> operator +(array<int, 11> A, array<int, 11> B){
array<int, 11> C;
for (int i = 0; i < 11; i++){
C[i] = modulo(A[i] + B[i], MODS[i]);
}
return C;
}
int main(){
long long M;
cin >> M;
long long D;
cin >> D;
long long N;
cin >> N;
int B;
cin >> B;
if (M == 0 && D == 0){
if (N % 2 == 0){
cout << 0 << endl;
} else {
cout << 1 << endl;
}
} else {
array<int, 11> m = get(M);
array<int, 11> d = get(D);
map<array<int, 11>, int> mp;
mp[m] = 0;
vector<array<int, 11>> h = {m};
int t = 0;
int ans;
while (true){
if (t == N){
ans = m[0] % B;
break;
}
t++;
m = modpow(m + d, m);
h.push_back(m);
if (mp.count(m) == 1){
int t2 = mp[m];
int p = (N - t2) % (t - t2) + t2;
ans = h[p][0] % B;
break;
}
mp[m] = t;
}
if (ans < 10){
cout << ans << endl;
} else {
cout << 'A' << endl;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0