Submit Info #12501

Problem Lang User Status Time Memory
Tetration Mod cpp Haar AC 256 ms 0.72 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.71 MiB
example_01 AC 3 ms 0.67 MiB
max_00 AC 47 ms 0.70 MiB
max_01 AC 48 ms 0.68 MiB
max_02 AC 47 ms 0.70 MiB
max_1000000000_00 AC 14 ms 0.72 MiB
max_1000000000_01 AC 14 ms 0.67 MiB
max_1000000000_02 AC 13 ms 0.67 MiB
max_998244353_00 AC 256 ms 0.67 MiB
max_998244353_01 AC 250 ms 0.68 MiB
max_998244353_02 AC 250 ms 0.72 MiB
random_00 AC 33 ms 0.72 MiB
random_01 AC 10 ms 0.67 MiB
random_02 AC 9 ms 0.68 MiB
random_03 AC 10 ms 0.67 MiB
random_04 AC 26 ms 0.67 MiB
small_00 AC 3 ms 0.48 MiB

#include <bits/stdc++.h> /** * @title Euler's totient function * @docs euler_phi_function.md */ int64_t totient(int64_t n){ int64_t ret = n; for(int64_t i = 2; i * i <= n; ++i){ if(n % i == 0){ ret -= ret / i; while(n % i == 0) n /= i; } } if(n != 1) ret -= ret / n; return ret; } /** * @title Mod power * @docs mod_power.md */ int64_t power(int64_t n, int64_t p, int64_t m){ int64_t ret = 1; while(p > 0){ if(p & 1) (ret *= n) %= m; (n *= n) %= m; p >>= 1; } return ret; } int tetration(int64_t a, int64_t b, int64_t m){ auto rec = [](auto &rec, int64_t a, int64_t b, int64_t m) -> int { if(b == 1) return a % m; if(b == 0) return 1 % m; if(b == 2){ bool c = a >= m; int64_t ret = 1; int64_t p = a; a %= m; while(p > 0){ if(p & 1) if((ret *= a) >= m) ret %= m, c = true; if((a *= a) >= m) a %= m, c = true; p >>= 1; } if(c) ret += m; return ret; } if(a == 0) return b % 2 == 1 ? 0 : 1; if(m == 1) return 1; int phi = totient(m); int p = rec(rec, a, b-1, phi); bool c = p >= phi; int64_t ret = 1; while(p > 0){ if(p & 1) if((ret *= a) >= m) ret %= m, c = true; if((a *= a) >= m) a %= m, c = true; p >>= 1; } if(c) ret += m; return ret; }; return rec(rec, a, b, m) % m; } int main(){ int T; std::cin >> T; while(T--){ int A, B, M; std::cin >> A >> B >> M; auto ans = tetration(A, B, M); std::cout << ans << "\n"; } return 0; }