結果

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

ソースコード

diff # 

def compute_transition(B, D):
    transition = {}
    for x_old in range(B):
        base = (x_old + D) % B
        if x_old == 0:
            x_new = 1 % B
        else:
            x_new = pow(base, x_old, B)
        transition[x_old] = x_new
    return transition

def find_cycle(initial_x, transition, B):
    visited = {}
    path = []
    current = initial_x
    step = 0
    while current not in visited:
        visited[current] = step
        path.append(current)
        current = transition[current]
        step += 1
    start = visited[current]
    cycle = path[start:]
    return start, cycle

def main():
    M = int(input())
    D = int(input())
    N = int(input())
    B = int(input())

    initial_x = M % B
    if initial_x < 0:
        initial_x += B

    transition = compute_transition(B, D)
    start, cycle = find_cycle(initial_x, transition, B)

    path = []
    current = initial_x
    step = 0
    visited = {}
    while current not in visited:
        visited[current] = step
        path.append(current)
        current = transition[current]
        step += 1

    if N < len(path):
        result = path[N]
    else:
        remaining = N - start
        cycle_length = len(cycle)
        idx = remaining % cycle_length
        result = cycle[idx]

    if B == 11 and result == 10:
        print('A')
    else:
        print(result)

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