結果

問題 No.181 A↑↑N mod M
ユーザー lam6er
提出日時 2025-04-16 15:42:01
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 698 bytes
コンパイル時間 207 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 53,796 KB
最終ジャッジ日時 2025-04-16 15:45:18
合計ジャッジ時間 2,851 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 35 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

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 //= i
            result -= result // i
        i += 1
    if n > 1:
        result -= result // n
    return result

def compute(A, N, M):
    if M == 1:
        return 0
    if N == 0:
        return 1 % M
    if N == 1:
        return A % M
    phi_m = euler_phi(M)
    exponent = compute(A, N-1, phi_m)
    d = math.gcd(A, M)
    if d == 1:
        return pow(A, exponent, M)
    else:
        return pow(A, exponent + phi_m, M)

A, N, M = map(int, sys.stdin.readline().split())
print(compute(A, N, M))
0