Submit Info #12052

Problem Lang User Status Time Memory
Tetration Mod cpp Bogdan AC 96 ms 0.73 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.68 MiB
example_01 AC 0 ms 0.71 MiB
max_00 AC 27 ms 0.72 MiB
max_01 AC 25 ms 0.72 MiB
max_02 AC 22 ms 0.73 MiB
max_1000000000_00 AC 14 ms 0.67 MiB
max_1000000000_01 AC 16 ms 0.72 MiB
max_1000000000_02 AC 17 ms 0.71 MiB
max_998244353_00 AC 95 ms 0.72 MiB
max_998244353_01 AC 95 ms 0.72 MiB
max_998244353_02 AC 96 ms 0.67 MiB
random_00 AC 16 ms 0.71 MiB
random_01 AC 0 ms 0.67 MiB
random_02 AC 4 ms 0.68 MiB
random_03 AC 8 ms 0.67 MiB
random_04 AC 15 ms 0.72 MiB
small_00 AC 2 ms 0.68 MiB

#ifdef DEBUG #define _GLIBCXX_DEBUG #endif //#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; vector < pair < int, int > > factorize(int M) { vector < pair < int, int > > f; for (int i = 2; 1LL * i * i <= M; i++) { if (M % i == 0) { int ex = 0; while (M % i == 0) { M /= i; ex++; } f.emplace_back(i, ex); } } if (M > 1) { f.emplace_back(M, 1); } return f; } int pw(int a, int b, int M) { if (b == 0) { return 1 % M; } if (b & 1) { return (1LL * a * pw(a, b - 1, M)) % M; } else { int res = pw(a, b / 2, M); return (1LL * res * res) % M; } } const int INF = 44; //что-то больше log int safe_pw(int a, int b) { if (b == 0) return 1; if (b & 1) { return min(INF, a * safe_pw(a, b - 1)); } else { int res = safe_pw(a, b / 2); return min(res * res, INF); } } int is_biggerINF(int a, int b) { if (b >= INF) return INF; if (b == 0) { return 1; } int p = is_biggerINF(a, b - 1); if (p >= INF) return INF; return safe_pw(a, p); } int solve(int a, int b, int M) { if (M == 1) { return 0; } if (b == 0) { return (1 % M); } if (b == 1) { return a % M; } auto fct = factorize(M); int ph = 1; for (auto& it : fct) { ph *= it.first - 1; for (int i = 0; i + 1 < it.second; i++) { ph *= it.first; } } int d = solve(a, b - 1, ph); if (is_biggerINF(a, b - 1) > d) d += ph; return pw(a, d, M); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // freopen("input.txt", "r", stdin); int tst; cin >> tst; while (tst--) { int a, b, M; cin >> a >> b >> M; cout << solve(a, b, M) << '\n'; } return 0; }