結果

問題 No.181 A↑↑N mod M
ユーザー lam6er
提出日時 2025-04-16 15:40:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,708 bytes
コンパイル時間 234 ms
コンパイル使用メモリ 82,520 KB
実行使用メモリ 53,152 KB
最終ジャッジ日時 2025-04-16 15:44:55
合計ジャッジ時間 3,293 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 36 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import gcd

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

def crt(residues):
    x = 0
    product = 1
    for mod, rem in residues:
        g, a, b = extended_gcd(product, mod)
        if (rem - x) % g != 0:
            return None
        lcm = product // g * mod
        tmp = ((rem - x) // g * a) % (mod // g)
        x += tmp * product
        product = lcm
        x %= product
    return x

def factor(m):
    factors = {}
    i = 2
    while i * i <= m:
        while m % i == 0:
            factors[i] = factors.get(i, 0) + 1
            m = m // i
        i += 1
    if m > 1:
        factors[m] = 1
    return factors

def euler_phi(n):
    if n == 0:
        return 0
    result = n
    i = 2
    while i * i <= n:
        if n % i == 0:
            while n % i == 0:
                n = n // i
            result -= result // i
        i += 1
    if n > 1:
        result -= result // n
    return result

def mod_tet_coprime(a, n, m):
    if m == 1:
        return 0
    if n == 0:
        return 1 % m
    if n == 1:
        return a % m
    phi = euler_phi(m)
    e = mod_tet_coprime(a, n-1, phi)
    if e == 0 and phi != 0:
        e += phi
    return pow(a, e, m)

def minimal_t(a, x):
    if x == 0:
        return 0
    current = 1
    t = 0
    while True:
        if current >= x:
            return t
        if t == 0:
            current = 1
        else:
            if a == 1:
                current = 1
            else:
                if current >= x:
                    return t
                next_current = a ** current
                if next_current >= x:
                    return t + 1
                else:
                    current = next_current
        t += 1
        if a == 1:
            return 0

def compute_tower(a, t):
    if t == 0:
        return 1
    res = 1
    for _ in range(t):
        res = a ** res
    return res

def mod_non_coprime(a, p, k, n):
    s = 0
    temp = a
    while temp % p == 0:
        s += 1
        temp = temp // p
    d = temp
    if n == 0:
        return 1 % (p**k)
    if n == 1:
        return a % (p**k)
    if s == 0:
        return mod_tet_coprime(a, n, p**k)
    else:
        if n == 2:
            e = a
            if s * e >= k:
                return 0
            else:
                part1 = pow(p, s * e, p**k)
                part2 = pow(d, e, p**(k - s * e))
                return (part1 * part2) % (p**k)
        else:
            x = (k + s - 1) // s
            if x == 0:
                t_needed = 0
            else:
                t_needed = minimal_t(a, x)
            if (n-1) >= t_needed:
                return 0
            else:
                e = compute_tower(a, n-1)
                if s * e >= k:
                    return 0
                else:
                    part1 = pow(p, s * e, p**k)
                    part2 = pow(d, e, p**(k - s * e))
                    return (part1 * part2) % (p**k)

def main():
    A, N, M = map(int, sys.stdin.readline().split())
    if M == 0:
        print(0)
        return
    if N == 0:
        print(1 % M)
        return
    factors = factor(M)
    residues = []
    for p, exp in factors.items():
        pk = p ** exp
        a_mod_pk = A % pk
        if a_mod_pk == 0:
            res = mod_non_coprime(A, p, exp, N)
        else:
            if gcd(A, p) == 1:
                res = mod_tet_coprime(A, N, pk)
            else:
                res = mod_non_coprime(A, p, exp, N)
        residues.append( (pk, res) )
    result = crt(residues)
    print(result % M)

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