Submit Info #39646

Problem Lang User Status Time Memory
Tetration Mod cpp-acl Lorent AC 245 ms 0.68 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
example_01 AC 1 ms 0.67 MiB
max_00 AC 40 ms 0.62 MiB
max_01 AC 41 ms 0.67 MiB
max_02 AC 40 ms 0.67 MiB
max_1000000000_00 AC 11 ms 0.67 MiB
max_1000000000_01 AC 12 ms 0.67 MiB
max_1000000000_02 AC 12 ms 0.68 MiB
max_998244353_00 AC 245 ms 0.65 MiB
max_998244353_01 AC 244 ms 0.61 MiB
max_998244353_02 AC 243 ms 0.68 MiB
random_00 AC 27 ms 0.58 MiB
random_01 AC 9 ms 0.67 MiB
random_02 AC 4 ms 0.66 MiB
random_03 AC 8 ms 0.67 MiB
random_04 AC 21 ms 0.62 MiB
small_00 AC 2 ms 0.67 MiB

#include <bits/stdc++.h> using namespace std; #include <atcoder/math> using namespace atcoder; long long euler_phi(long long n) { long long res = n; for (long long i = 2; i * i <= n; ++i) { if (n % i == 0) { res = res / i * (i - 1); while (n % i == 0) n /= i; } } if (n != 1) res = res / n * (n - 1); return res; } long long tetration_mod(long long a, long long b, long long m) { if (m == 1) return 0; if (a == 0) return b % 2 == 0 ? 1 : 0; if (b == 0) return 1; if (b == 1) return a % m; if (b == 2) return pow_mod(a, a, m); long long phi = euler_phi(m); return pow_mod(a, tetration_mod(a, b - 1, phi) + phi, m); } void solve() { int a, b, m; cin >> a >> b >> m; cout << tetration_mod(a, b, m) << '\n'; } int main() { int t; cin >> t; while (t--) solve(); }