結果

問題 No.3396 ChRisTmas memory
コンテスト
ユーザー KumaTachiRen
提出日時 2025-11-12 16:47:56
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,194 bytes
コンパイル時間 309 ms
コンパイル使用メモリ 82,492 KB
実行使用メモリ 85,804 KB
最終ジャッジ日時 2025-12-02 23:31:38
合計ジャッジ時間 43,572 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30 MLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

def inv_mod(x, m):
    x %= m
    a, b = m, x
    u, v = 0, 1
    while b > 0:
        q = a // b
        a, b = b, a - q * b
        u, v = v, u - q * v
    return 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, g, y = 1, 1, r % m
            for i in range(len(M)):
                y = (y - Y[i] * p) % m
                p = p * M[i] % m
                g = gcd(g * M[i], m)
            if y % g != 0:
                M.append(1), Y.append(-1)
            else:
                m //= g
                y = 0 if m == 1 else (y // g) * inv_mod(p // g, m) % 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