結果

問題 No.3396 ChRisTmas memory
コンテスト
ユーザー KumaTachiRen
提出日時 2025-11-12 21:17:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,656 ms / 4,000 ms
コード長 1,093 bytes
コンパイル時間 296 ms
コンパイル使用メモリ 82,844 KB
実行使用メモリ 78,020 KB
最終ジャッジ日時 2025-12-02 23:32:01
合計ジャッジ時間 21,951 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def inv_mod(x, m):
    a, b = m, x % m
    u, v = 0, 1
    while b > 0:
        q = a // b
        a, b = b, a - q * b
        u, v = v, u - q * v
    return a, u

Q = int(input())
M, Y = [], []
for _ in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        m, r = query[1], query[2]
        if len(Y) > 0 and Y[-1] < 0:
            M.append(1), Y.append(-1)
        else:
            p, y = 1, r % m
            for i in range(len(M)):
                y = (y - Y[i] * p) % m
                p = p * M[i] % m
            g, x = inv_mod(p, m)
            if y % g != 0:
                M.append(1), Y.append(-1)
            else:
                m //= g
                y = 0 if m == 1 else (y // g) * x % m
                M.append(m), Y.append(y)
    elif query[0] == 2:
        k = query[1]
        del M[-k:]
        del Y[-k:]
    else:
        m = query[1]
        if len(Y) > 0 and Y[-1] < 0:
            print(-1)
        else:
            x = 0
            for i in range(len(M) - 1, -1, -1):
                x = (x * M[i] + Y[i]) % m
            print(x)
0