結果

問題 No.3396 ChRisTmas memory
コンテスト
ユーザー KumaTachiRen
提出日時 2025-11-12 23:26:57
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 1,714 ms / 4,000 ms
コード長 1,186 bytes
コンパイル時間 932 ms
コンパイル使用メモリ 112,464 KB
実行使用メモリ 28,416 KB
最終ジャッジ日時 2025-12-02 23:32:49
合計ジャッジ時間 20,004 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
raw source code 

using System;

(long g, long inv) InvMod(long x, long m) {
  long a = m, b = x % m;
  if (b < 0) b += m;
  long u = 0, v = 1;
  while (b > 0) {
    long q = a / b;
    (a, b) = (b, a - q * b);
    (u, v) = (v, u - q * v);
  }
  if (u < 0) u += m / a;
  return (a, u);
}

int Q = int.Parse(Console.ReadLine());
var M = new int[Q];
var Y = new int[Q];
int N = 0;
while (Q-- > 0) {
	var query = Console.ReadLine().Split(' ');
	int t = int.Parse(query[0]);
	if (t == 1) {
		int m = int.Parse(query[1]);
		int r = int.Parse(query[2]);
		if (N > 0 && Y[N - 1] < 0) {
			M[N] = m; Y[N] = -1;
		} else {
			long p = 1, y = r % m;
			for (int i = 0; i < N; i++) {
				y -= Y[i] * p % m;
				if (y < 0) y += m;
				p = p * M[i] % m;
			}
			var (g, x) = InvMod(p, m);
			if (y % g != 0) {
				M[N] = 1; Y[N] = -1;
			} else {
				M[N] = m /= (int)g;
				Y[N] = (int)((y / g) * x % m);
			}
		}
		N++;
	} else if (t == 2) {
		int k = int.Parse(query[1]);
		N -= k;
	} else if (t == 3) {
		int m = int.Parse(query[1]);
		if (N > 0 && Y[N - 1] < 0) {
			Console.WriteLine(-1);
		} else {
			long x = 0;
			for (int i = N - 1; i >= 0; i--) x = (x * M[i] + Y[i]) % m;
			Console.WriteLine(x);
		}
	}
}
0