読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

yukicoder : No.186 中華風 (Easy)

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

問題

整数 X_1, X_2, X_3, Y_1, Y_2, Y_3が与えられる。
 P \mod Y_i = X_iを満たす最小の正整数Pが存在すれば、それを返せ。

解法

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

ここで、整数jに対し Q = P + LCM(Y_1,Y_2) * jとなるQを考えると、このQは同様に X_1, X_2, Y_1, Y_2について条件を満たす。
よって同様に 0 \le j \le Y_3の範囲で上記Qを総当たりし、 Q \mod Y_3 = X_3となるものを探せばよい。

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");
}

まとめ

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

広告を非表示にする