結果

問題 No.3396 ChRisTmas memory
コンテスト
ユーザー to-omer
提出日時 2025-12-03 22:08:36
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 3,813 ms / 4,000 ms
コード長 1,431 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 12,032 KB
最終ジャッジ日時 2025-12-03 22:09:10
合計ジャッジ時間 34,049 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from math import gcd


def extgcd(a, b):
    u, v, x, y = 1, 0, 0, 1
    while a != 0:
        k = b // a
        x -= k * u
        y -= k * v
        b -= k * a
        x, u = u, x
        y, v = v, y
        b, a = a, b
    return b, x, y


def modinv(a, m):
    g, x, y = extgcd(a, m)
    if g != 1:
        raise ValueError("Inverse doesn't exist")
    else:
        return x % m


def main():
    Q = int(input())
    M, R = 1, 0
    hist = []
    for _ in range(Q):
        t, *args = map(int, input().split())
        if t == 1:
            if R == -1:
                hist.append((-1, R))
                continue
            m, r = args
            b = (r - R % m) % m
            a = M
            g = gcd(a, m)
            if b % g != 0:
                hist.append((-1, R))
                R = -1
                continue
            a //= g
            b //= g
            m //= g
            b = (b * modinv(a % m, m)) % m
            R += b * M
            M *= m
            hist.append((m, b))
        elif t == 2:
            (k,) = args
            for _ in range(k):
                m, b = hist.pop()
                if m == -1:
                    R = b
                else:
                    M //= m
                    R -= b * M
        else:
            (m,) = args
            if R == -1:
                print(-1)
            else:
                print(R % m)


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