結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー kgprac
提出日時 2025-03-17 17:56:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 565 bytes
コンパイル時間 2,082 ms
コンパイル使用メモリ 197,312 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-17 17:56:40
合計ジャッジ時間 3,142 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
template<class T>
pair<T,T>ginv(T a,T m){
	T b=a,u=0,v=1;
	a=m;
	while(b){
		T q=a/b;
		a-=q*b,swap(a,b);
		u-=q*v,swap(u,v);
	}
	if(u<0)u+=m/a;
	return{a,u};
}
template<class T>
pair<T,T>crt(T a,T m,T b,T n){
	if(m<n)swap(m,n),swap(a,b);
	auto[g,iu]=ginv(m,n);
	if((b-a)%g)return{0,0};
	T v=n/g;
	T k=(b-a)/g%v*iu%v;
	if(k<0)k+=v;
	return{a+k*m,m*v};
}
int main(){
	long a,b,c,d,e,f;
	cin>>a>>b>>c>>d>>e>>f;
	tie(a,b)=crt(a,b,c,d);
	tie(a,b)=crt(a,b,e,f);
	if(a==0)a+=b;
	if(b==0)cout<<-1<<'\n';
	else cout<<a<<'\n';
}
0