結果

問題 No.181 A↑↑N mod M
ユーザー lam6er
提出日時 2025-03-31 17:47:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,523 bytes
コンパイル時間 441 ms
コンパイル使用メモリ 82,488 KB
実行使用メモリ 54,720 KB
最終ジャッジ日時 2025-03-31 17:48:20
合計ジャッジ時間 3,433 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 27 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import gcd

def input():
    return sys.stdin.read()

def factorize(n):
    factors = []
    count = 0
    while n % 2 == 0:
        count += 1
        n //= 2
    if count > 0:
        factors.append((2, count))
    i = 3
    while i * i <= n:
        count = 0
        while n % i == 0:
            count += 1
            n //= i
        if count > 0:
            factors.append((i, count))
        i += 2
    if n > 1:
        factors.append((n, 1))
    return factors

def euler_phi(n):
    if n == 0:
        return 0
    result = 1
    factors = factorize(n)
    for (p, k) in factors:
        result *= (p ** (k - 1)) * (p - 1)
    return result

def extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        g, x, y = extended_gcd(b, a % b)
        return (g, y, x - (a // b) * y)

def crt(remainders):
    x = 0
    product = 1
    for a, m in remainders:
        g, p, q = extended_gcd(product, m)
        if (a - x) % g != 0:
            return None
        lcm = product // g * m
        tmp = ((a - x) // g * p) % (m // g)
        x += product * tmp
        product = lcm
        x %= product
    return x % product if product != 0 else 0

def compute_pow_mod(a, b, p, k):
    mod = p ** k
    if a % p == 0:
        s = 0
        tmp = a
        while tmp % p == 0:
            s += 1
            tmp //= p
        if s * b >= k:
            return 0
        else:
            remaining_mod = pow(tmp, b, mod)
            p_pow = pow(p, s * b, mod)
            res = (p_pow * remaining_mod) % mod
            return res
    else:
        if mod == 1:
            return 0
        phi = (p ** (k - 1)) * (p - 1)
        e = b % phi
        if e == 0 and b != 0:
            e = phi
        return pow(a, e, mod)

def pow_mod_helper(a, b, mod):
    if mod == 1:
        return 0
    factors = factorize(mod)
    prime_powers = [(p, k) for (p, k) in factors]
    remainders = []
    for (p, k) in prime_powers:
        pk = p ** k
        rem = compute_pow_mod(a, b, p, k)
        remainders.append((rem, pk))
    return crt(remainders) if remainders else 0

def tet_mod(A, n, m):
    if m == 1:
        return 0
    if n == 0:
        return 1 % m
    elif n == 1:
        return A % m
    else:
        phi = euler_phi(m)
        if phi == 0:
            return 0
        exponent = tet_mod(A, n-1, phi)
        return pow_mod_helper(A, exponent, m)

def main():
    A, N, M = map(int, input().split())
    print(tet_mod(A, N, M))

if __name__ == '__main__':
    main()
0