結果

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

ソースコード

diff # 

import sys
import math
from math import gcd

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

def crt(remainders, moduli):
    x = 0
    product = 1
    for m in moduli:
        product *= m
    
    for rm, m in zip(remainders, moduli):
        Mi = product // m
        x += rm * Mi * pow(Mi, -1, m)
    return x % product

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

def solve_prime_power(p, k, A, N):
    s = 0
    a = A
    while a % p == 0 and a != 0:
        s += 1
        a //= p
    
    current_mod = p ** k
    
    if N == 0:
        return 1 % current_mod
    
    if s == 0:
        def recurse(n, mod):
            if mod == 1:
                return 0
            if n == 0:
                return 1 % mod
            if n == 1:
                return A % mod
            phi = euler_phi(mod)
            e = recurse(n-1, phi)
            return pow(A, e + (phi if e < phi else 0), mod)
        return recurse(N, current_mod)
    else:
        if s * 1 >= k:
            return 0
        if N == 1:
            return (A % current_mod)
        a_prime = A // (p ** s)
        if N == 2:
            e = A
            if s * e >= k:
                return 0
            else:
                part1 = pow(p, s * e, current_mod)
                part2 = pow(a_prime, e, current_mod // (p ** (s * e)))
                return (part1 * part2) % current_mod
        if N >= 3:
            return 0

def main():
    A, N, M = map(int, sys.stdin.readline().split())
    if M == 1:
        print(0)
        return
    if N == 0:
        print(1 % M)
        return
    
    factors = factorize(M)
    moduli = []
    remainders = []
    for p, exp in factors.items():
        pk = p ** exp
        remainder = solve_prime_power(p, exp, A, N)
        remainders.append(remainder)
        moduli.append(pk)
    
    result = crt(remainders, moduli)
    print(result % M)

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