yukicoder : No.186 中華風 (Easy)

ライブラリ貼り付けたけどなぜかうまく通らなかったので、普通に解いた。
http://yukicoder.me/problems/447

問題

整数が与えられる。
を満たす最小の正整数Pが存在すれば、それを返せ。

解法

タイトルから解法はバレバレであるが、なぜかライブラリ貼り付けたら失敗したので別解を記載する。
まずについて考える。
の範囲でとなるPを総当たりし、となるものを探せばよい。
は自明なので、このPはについて条件を満たす。

ここで、整数jに対しとなるQを考えると、このQは同様にについて条件を満たす。
よって同様にの範囲で上記Qを総当たりし、となるものを探せばよい。

ll X[1010],Y[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,3) cin>>X[i]>>Y[i];
	ll xx=0,yy;
	for(i=0;i<=Y[1];i++) {
		if(X[0]+Y[0]*i>0 && ((X[0]+Y[0]*i) % Y[1]==X[1])) {
			xx=X[0]+Y[0]*i;
			yy=Y[0]*Y[1]/__gcd(Y[0],Y[1]);
			break;
		}
	}
	if(xx==0) return _P("-1\n");
	for(i=0;i<=Y[2];i++) {
		if(xx+yy*i>0 && ((xx+yy*i) % Y[2]==X[2])) return _P("%lld\n",xx+yy*i);
	}
	return _P("-1\n");
}

まとめ

ライブラリが動かなくてもなんとかなるものです。