Submit Info #27364

Problem Lang User Status Time Memory
Tetration Mod cpp golikovnik AC 87 ms 0.70 MiB

ケース詳細
Name Status Time Memory
example_00 AC 3 ms 0.66 MiB
example_01 AC 1 ms 0.62 MiB
max_00 AC 19 ms 0.67 MiB
max_01 AC 20 ms 0.66 MiB
max_02 AC 15 ms 0.60 MiB
max_1000000000_00 AC 9 ms 0.67 MiB
max_1000000000_01 AC 13 ms 0.48 MiB
max_1000000000_02 AC 10 ms 0.67 MiB
max_998244353_00 AC 82 ms 0.62 MiB
max_998244353_01 AC 87 ms 0.67 MiB
max_998244353_02 AC 82 ms 0.70 MiB
random_00 AC 14 ms 0.67 MiB
random_01 AC 6 ms 0.67 MiB
random_02 AC 1 ms 0.62 MiB
random_03 AC 6 ms 0.67 MiB
random_04 AC 10 ms 0.62 MiB
small_00 AC 2 ms 0.67 MiB

// Copyright 2020 Nikita Golikov #include <bits/stdc++.h> using namespace std; using i64 = int64_t; using ui64 = uint64_t; template <class A, class B> bool smin(A &x, B &&y) { if (y < x) { x = y; return true; } return false; } template <class A, class B> bool smax(A &x, B &&y) { if (x < y) { x = y; return true; } return false; } int mul(i64 x, int y, int mod) { return (int) (x * y % mod); } int pw(int x, i64 y, int mod) { int r = 1; while (y) { if (y & 1) { r = mul(r, x, mod); } x = mul(x, x, mod); y >>= 1; } return r; } int phi(int x) { int r = x; for (int p = 2; p * p <= x; ++p) { if (x % p == 0) { r /= p; r *= p - 1; while (x % p == 0) { x /= p; } } } if (x > 1) { r /= x; r *= x - 1; } return r; } int tetration(int a, int b, int mod) { if (mod == 1) { return 0; } if (a == 0) { return 1 - b % 2; } if (a == 1) { return 1; } if (b == 0) { return 1; } if (b == 1) { return a % mod; } if (b == 2) { return pw(a, a, mod); } if (b == 3) { if (a == 2) { return 16 % mod; } if (a == 3) { return pw(3, 27, mod); } } if (b == 4) { if (a == 2) { return 65536 % mod; } } auto phi_mod = phi(mod); auto deg = tetration(a, b - 1, phi_mod); return pw(a, (i64) deg + phi_mod, mod); } void solve(int) { int a, b, mod; cin >> a >> b >> mod; cout << tetration(a, b, mod) << '\n'; } int main() { #ifdef GOLIKOV assert(freopen("in", "rt", stdin)); auto _clock_start = chrono::high_resolution_clock::now(); #endif ios::sync_with_stdio(false); cin.tie(nullptr); int tests; cin >> tests; for (int _tt = 1; _tt <= tests; ++_tt) { solve(_tt); } #ifdef GOLIKOV cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( chrono::high_resolution_clock::now() - _clock_start).count() << "ms." << endl; #endif return 0; }