Submit Info #54443

Problem Lang User Status Time Memory
Tetration Mod cpp wleungBVG AC 248 ms 0.72 MiB

ケース詳細
Name Status Time Memory
2_3_32_00 AC 1 ms 0.61 MiB
example_00 AC 1 ms 0.61 MiB
example_01 AC 1 ms 0.61 MiB
max_00 AC 40 ms 0.70 MiB
max_01 AC 39 ms 0.72 MiB
max_02 AC 39 ms 0.71 MiB
max_1000000000_00 AC 12 ms 0.71 MiB
max_1000000000_01 AC 13 ms 0.71 MiB
max_1000000000_02 AC 11 ms 0.71 MiB
max_998244353_00 AC 248 ms 0.71 MiB
max_998244353_01 AC 244 ms 0.61 MiB
max_998244353_02 AC 243 ms 0.71 MiB
random_00 AC 27 ms 0.71 MiB
random_01 AC 8 ms 0.61 MiB
random_02 AC 4 ms 0.71 MiB
random_03 AC 8 ms 0.71 MiB
random_04 AC 21 ms 0.71 MiB
small_00 AC 1 ms 0.71 MiB

// https://judge.yosupo.jp/problem/tetration_mod #include <bits/stdc++.h> using namespace std; template <class C> constexpr int sz(const C &c) { return int(c.size()); } constexpr const char nl = '\n', sp = ' '; using uint = unsigned int; using ll = long long; using ull = unsigned long long; using ld = long double; #if __SIZEOF_INT128__ using i128 = __int128_t; using ui128 = __uint128_t; #endif template <class T> T phi(T x) { T ret = x; for (T i = 2; i * i <= x; i++) if (x % i == 0) for (ret -= ret / i; x % i == 0; x /= i); if (x > 1) ret -= ret / x; return ret; } template <class T> T mulMod(T a, T b, T mod) { return a * b % mod; } template <class T, class U> T powMod(T base, U pow, T mod) { T x = 1; while (true) { if (pow % 2 == 1) x = mulMod(x, base, mod); if ((pow /= 2) == 0) break; base = mulMod(base, base, mod); } return x; } template <class T, class U> T tetraMod(T a, U n, T mod) { if (mod == T(1)) return T(0); if (a == T(0)) return (T(1) - T(n % U(2))) % mod; if (n == U(0)) return T(1) % mod; if (n == U(1)) return a % mod; if (n == U(2)) return powMod(a % mod, a, mod); T p = phi(mod), ret = tetraMod(a, n - 1, p); if (ret == 0) ret += p; return powMod(a % mod, ret, mod); } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // freopen("err.txt", "w", stderr); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; cin >> T; for (int ti = 0; ti < T; ti++) { ll A, B, M; cin >> A >> B >> M; cout << tetraMod(A, B, M) << nl; } return 0; }