結果

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

ソースコード

diff # 

def main():
    import sys
    M, D, N, B = map(int, sys.stdin.read().split())
    
    if N == 0:
        result = M % B
        print(result if result < 10 else 'A')
        return
    
    D_mod = D % B
    
    next_state = []
    for i in range(B):
        a = (i + D_mod) % B
        if i == 0:
            res = 1 % B if a == 0 else 1 % B
        else:
            if a == 0:
                res = 0 % B
            else:
                res = pow(a, i, B)
        next_state.append(res)
    
    current = M % B
    history = [current]
    for _ in range(B):
        current = next_state[current]
        if current in history:
            idx = history.index(current)
            pre = history[:idx]
            cycle = history[idx:]
            break
        history.append(current)
    else:
        pre = history
        cycle = []
    
    if N < len(history):
        answer = history[N]
    else:
        len_pre = len(pre)
        len_cycle = len(cycle)
        remaining = N - len_pre
        if len_cycle == 0:
            answer = history[-1]
        else:
            answer = cycle[remaining % len_cycle]
    
    if answer < 10:
        print(answer)
    else:
        print('A')

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