結果

問題 No.3396 ChRisTmas memory
コンテスト
ユーザー id-ord
提出日時 2026-01-07 19:43:25
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 1,991 ms / 4,000 ms
コード長 857 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,446 ms
コンパイル使用メモリ 148,512 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2026-01-07 19:43:48
合計ジャッジ時間 22,880 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
using i64=int64_t;
struct data{i64 M;i64 R;i64 nx;i64 nr;} stack[10000];
int szStack;
i64 Xmod(i64 m){
	i64 x=0,r=1;
	for(int i=0;i<szStack;i++){
		if(stack[i].M==0)return -1;
		x+=stack[i].nx*r;x%=m;
		r*=stack[i].nr;r%=m;
	}
	return x;
}
i64 Rmod(i64 m){
	i64 r=1;
	for(int i=0;i<szStack;i++){
		r*=stack[i].nr;r%=m;
	}
	return r;
}
i64 extgcd(i64 a,i64 b,i64 &x,i64 &y){
	i64 d=a;
	if(b){d=extgcd(b,a%b,y,x);y-=(a/b)*x;}
	else{x=1;y=0;}
	return d;
}
int main(){int Q;std::cin>>Q;while(Q--){
	i64 q,x,y;
	std::cin>>q>>x;
	if(q==1){
		std::cin>>y;
		i64 a=Xmod(x),b=Rmod(x),t,u,g;
		if(a==-1){stack[szStack++]={};continue;}
		g=extgcd(x,b,t,u);
		if((y-a)%g){stack[szStack++]={};continue;}
		if(u<0)u+=x/g;
		u*=(y-a+x)/g;u%=x/g;
		stack[szStack++]={x,y,u,x/g};
	}
	if(q==2){szStack-=x;}
	if(q==3){std::cout<<Xmod(x)<<"\n";}
}return 0;}
0