結果

問題 No.3396 ChRisTmas memory
コンテスト
ユーザー KumaTachiRen
提出日時 2025-11-12 17:35:17
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 1,178 bytes
コンパイル時間 2,124 ms
コンパイル使用メモリ 112,056 KB
実行使用メモリ 28,892 KB
最終ジャッジ日時 2025-12-02 23:31:19
合計ジャッジ時間 33,138 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 30 TLE * 1 -- * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 Gcd(long a, long b) {
	while (b != 0) (a, b) = (b, a % b);
	return a;
}

long InvMod(long x, long m) {
  long a = m, b = x;
  long u = 0, v = 1;
  while (b != 0) {
    long q = a / b;
    (a, b) = (b, a - q * b);
    (u, v) = (v, u - q * v);
  }
  u %= m;
  return u < 0 ? u + m : 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, g = 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;
				g = Gcd(g * M[i], m);
			}
			if (y % g != 0) {
				M[N] = 1; Y[N] = -1;
			} else {
				M[N] = m /= (int)g;
				Y[N] = m == 1 ? 0 : (int)((y / g) * InvMod(p / g, m) % m);
			}
		}
		N++;
	} else if (t == 2) {
		int k = int.Parse(query[1]);
		N -= k;
	} else if (t == 3) {
		int m = int.Parse(query[1]);
		long x = 0;
		for (int i = N - 1; i >= 0; i--) x = (x * M[i] + Y[i]) % m;
		Console.WriteLine(m);
	}
}
0