結果

問題 No.2193 メガの下１桁
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:40:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,126 bytes
コンパイル時間 496 ms
コンパイル使用メモリ 82,056 KB
実行使用メモリ 53,840 KB
最終ジャッジ日時 2025-04-16 00:43:33
合計ジャッジ時間 3,040 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

def compute_next_state(s, D_mod, B):
    a = (s + D_mod) % B
    e = s
    if a == 0 and e == 0:
        return 1 % B
    elif a == 0:
        return 0 % B
    else:
        return pow(a, e, B)

M = int(input())
D = int(input())
N = int(input())
B = int(input())

if N == 0:
    print(M % B)
    exit()

D_mod = D % B
s0 = M % B

states = [s0]
seen = {s0: 0}
pre = -1
cycle = []

for i in range(1, B + 1):
    current = compute_next_state(states[-1], D_mod, B)
    if current in seen:
        pre = seen[current]
        cycle = states[pre:]
        cycle_length = len(cycle)
        break
    seen[current] = i
    states.append(current)
else:
    # This should not happen as per pigeonhole principle
    cycle = []
    cycle_length = 0

if pre == -1:
    # Fallback in case no cycle found (though theoretically impossible)
    if N < len(states):
        result = states[N]
    else:
        result = states[-1]
else:
    if N < len(states):
        result = states[N]
    else:
        remaining_steps = N - pre
        result = cycle[remaining_steps % cycle_length]

if result >= 10:
    print('A')
else:
    print(result)
0