Submit Info #39705

Problem Lang User Status Time Memory
Tetration Mod cpp Lorent AC 251 ms 0.67 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.62 MiB
example_01 AC 1 ms 0.67 MiB
max_00 AC 43 ms 0.67 MiB
max_01 AC 44 ms 0.67 MiB
max_02 AC 43 ms 0.65 MiB
max_1000000000_00 AC 14 ms 0.67 MiB
max_1000000000_01 AC 14 ms 0.67 MiB
max_1000000000_02 AC 15 ms 0.64 MiB
max_998244353_00 AC 251 ms 0.67 MiB
max_998244353_01 AC 250 ms 0.67 MiB
max_998244353_02 AC 249 ms 0.67 MiB
random_00 AC 30 ms 0.67 MiB
random_01 AC 9 ms 0.67 MiB
random_02 AC 3 ms 0.67 MiB
random_03 AC 10 ms 0.65 MiB
random_04 AC 26 ms 0.45 MiB
small_00 AC 2 ms 0.59 MiB

#include <bits/stdc++.h> using namespace std; long long pow_mod(long long a, long long n, long long m) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % m; a = a * a % m; n >>= 1; } return res; } 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(); }