Submit Info #53101

Problem Lang User Status Time Memory
Tetration Mod pypy3 toyuzuko AC 430 ms 33.18 MiB

ケース詳細
Name Status Time Memory
2_3_32_00 AC 47 ms 29.82 MiB
example_00 AC 48 ms 29.81 MiB
example_01 AC 47 ms 29.81 MiB
max_00 AC 161 ms 33.18 MiB
max_01 AC 175 ms 32.19 MiB
max_02 AC 160 ms 32.05 MiB
max_1000000000_00 AC 110 ms 32.57 MiB
max_1000000000_01 AC 112 ms 32.32 MiB
max_1000000000_02 AC 112 ms 32.30 MiB
max_998244353_00 AC 427 ms 32.44 MiB
max_998244353_01 AC 430 ms 32.68 MiB
max_998244353_02 AC 426 ms 32.42 MiB
random_00 AC 133 ms 32.19 MiB
random_01 AC 82 ms 31.43 MiB
random_02 AC 72 ms 31.44 MiB
random_03 AC 91 ms 32.82 MiB
random_04 AC 117 ms 32.06 MiB
small_00 AC 76 ms 30.56 MiB

def euler_phi(n): if n == 1: return 1 res = 1 x = n y = 2 while y * y <= x: k = 0 while x % y == 0: k += 1 x //= y if k: res *= y**(k - 1) * (y - 1) y += 1 if x > 1: res *= x - 1 return res def tetration(a, n, mod): if mod == 1: return 0 if a == 0: return ~n & 1 if n == 0: return 1 if n == 1: return a % mod if n == 2: return pow(a, a, mod) p = euler_phi(mod) tmp = tetration(a, n - 1, p) if tmp: return pow(a, tmp, mod) else: return pow(a, p, mod) N = int(input()) for _ in range(N): a, n, mod = map(int, input().split()) print(tetration(a, n, mod))