結果
問題 | No.2193 メガの下1桁 |
ユーザー |
![]() |
提出日時 | 2023-01-13 22:32:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,606 bytes |
コンパイル時間 | 2,297 ms |
コンパイル使用メモリ | 178,348 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-24 18:17:50 |
合計ジャッジ時間 | 3,600 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 WA * 4 |
ソースコード
#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;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;}}