Submit Info #25108

Problem Lang User Status Time Memory
Tetration Mod python3 longrun AC 2414 ms 3.93 MiB

ケース詳細
Name Status Time Memory
example_00 AC 16 ms 3.86 MiB
example_01 AC 18 ms 3.82 MiB
max_00 AC 387 ms 3.85 MiB
max_01 AC 381 ms 3.86 MiB
max_02 AC 379 ms 3.90 MiB
max_1000000000_00 AC 118 ms 3.93 MiB
max_1000000000_01 AC 115 ms 3.90 MiB
max_1000000000_02 AC 115 ms 3.88 MiB
max_998244353_00 AC 2414 ms 3.90 MiB
max_998244353_01 AC 2414 ms 3.86 MiB
max_998244353_02 AC 2407 ms 3.88 MiB
random_00 AC 266 ms 3.89 MiB
random_01 AC 87 ms 3.82 MiB
random_02 AC 58 ms 3.82 MiB
random_03 AC 92 ms 3.89 MiB
random_04 AC 209 ms 3.91 MiB
small_00 AC 22 ms 3.86 MiB

def modpow(x, n, m): res = 1 while n: if n % 2: res = (res * x) % m x = (x * x) % m n >>= 1 return res def factorize(n): res = [] while n % 2 == 0: res.append(2) n //= 2 f = 3 while f * f <= n: if n % f == 0: res.append(f) n //= f else: f += 2 if n != 1: res.append(n) return res def totient(n): li = [] res = n if n % 2 == 0: li.append(2) while n % 2 == 0: n //= 2 f = 3 while f * f <= n: if n % f == 0: li.append(f) while n % f == 0: n //= f f += 2 if n != 1: li.append(n) for a in li: res //= a res *= (a-1) return res def mod_tetration(a, b, m): if(m == 1): return 0 if(a == 0): return 1-b%2 if(b == 0): return 1 if(b == 1): return a%m if(b == 2): return modpow(a, a, m) phi = totient(m) nb = mod_tetration(a, b-1, phi) + phi return modpow(a, nb, m) t = int(input()) for i in range(t): a, b, m = map(int, input().split()) print(mod_tetration(a, b, m))