Submit Info #33649

Problem Lang User Status Time Memory
Tetration Mod python3 Eki1009 AC 425 ms 4.17 MiB

ケース詳細
Name Status Time Memory
example_00 AC 20 ms 4.15 MiB
example_01 AC 20 ms 4.16 MiB
max_00 AC 161 ms 4.16 MiB
max_01 AC 161 ms 4.16 MiB
max_02 AC 154 ms 4.16 MiB
max_1000000000_00 AC 138 ms 4.16 MiB
max_1000000000_01 AC 141 ms 4.07 MiB
max_1000000000_02 AC 137 ms 4.17 MiB
max_998244353_00 AC 425 ms 4.15 MiB
max_998244353_01 AC 424 ms 4.09 MiB
max_998244353_02 AC 420 ms 4.12 MiB
random_00 AC 118 ms 4.14 MiB
random_01 AC 50 ms 4.11 MiB
random_02 AC 30 ms 4.16 MiB
random_03 AC 49 ms 4.12 MiB
random_04 AC 95 ms 4.10 MiB
small_00 AC 23 ms 4.07 MiB

def prime_table(m=10**9): thres = int(m ** 0.5 + 1) flg = [0] * (thres + 1) i = 2 while i * i <= thres: if not flg[i]: for j in range(i * i, thres + 1, i): flg[j] = 1 i += 1 res = [] for i in range(2, thres + 1): if not flg[i]: res.append(i) return res ps = prime_table() def tetration(a, b, m): def totient(n): res = n for p in ps: if p * p > n: break if n % p == 0: res = res // p * (p - 1) while n % p == 0: n //= p if n != 1: res = res // n * (n - 1) return res def mpow(a, p, m): res, flg = 1 % m, 1 while p: if p & 1: res *= a if res >= m: flg = 0 res %= m if p == 1: break a *= a if a >= m: flg = 0 a %= m p >>= 1 return res, flg def calc(a, b, m): if a == 0: return (b & 1) ^ 1, 1 if a == 1: return 1, 1 if m == 1: return 0, 0 if b == 0: return 1, 1 if b == 1: return a % m, int(a < m) phi_m = totient(m) pre, flg1 = calc(a, b - 1, phi_m) if flg1: res, flg2 = mpow(a % m, pre, m) else: res, flg2 = mpow(a % m, pre + phi_m, m) return res, flg1 & flg2 return calc(a, b, m)[0] % m import sys input = sys.stdin.readline t = int(input()) for _ in range(t): a, b, m = map(int, input().split()) print(tetration(a, b, m))