Submit Info #5804

Problem Lang User Status Time Memory
Tetration Mod python3 convexineq AC 841 ms 4.05 MiB

ケース詳細
Name Status Time Memory
example_00 AC 15 ms 3.98 MiB
example_01 AC 15 ms 4.03 MiB
max_00 AC 530 ms 3.97 MiB
max_01 AC 535 ms 4.03 MiB
max_02 AC 537 ms 3.99 MiB
max_1000000000_00 AC 139 ms 4.04 MiB
max_1000000000_01 AC 130 ms 4.03 MiB
max_1000000000_02 AC 136 ms 4.01 MiB
max_998244353_00 AC 838 ms 4.00 MiB
max_998244353_01 AC 841 ms 3.98 MiB
max_998244353_02 AC 833 ms 4.04 MiB
random_00 AC 376 ms 3.99 MiB
random_01 AC 129 ms 4.00 MiB
random_02 AC 64 ms 4.00 MiB
random_03 AC 127 ms 4.05 MiB
random_04 AC 305 ms 4.04 MiB
small_00 AC 18 ms 3.99 MiB

def totient(N): #トーシェント関数 res = N if N&1==0: res //= 2 while N%2 == 0: N //= 2 M = int(N**0.5)+1 for i in range(3,M,2): 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 def tetration_mod(a,n,MOD): #a↑↑n mod MOD を求める if a==0: return (1-(n&1))%MOD if a==1: return 1%MOD if n==0: return 1%MOD if n==1: return a%MOD return pow(a,tetration_amend(a,n-1,totient(MOD)),MOD)%MOD def tetration_amend(a,n,MOD): # #a↑↑n mod MOD (ただし周期修正あり)を求める # 小さくて周期に入っていない if n==0: return 1 if n==1: return a if a==2: if n==2: return 4 if n==3: return 16 if a==3 and n==2: return 27 # MOD=1 の場合は値が確定 if MOD == 1: return 65 #でかい x = pow(a,tetration_amend(a,n-1,totient(MOD)),MOD) if x >= 65: return x else: return x + (65+MOD)//MOD*MOD Q = int(input()) for _ in range(Q): a,b,m = map(int,input().split()) print(tetration_mod(a,b,m))