Codeforces #360 Div1 B. Remainders Game

今回難易度低め？
http://codeforces.com/contest/687/problem/B

問題

Xが不明であるとき、X mod Kを求めたい。
数列C[i]対し、X mod C[i]がすべてわかればX mod Kもわかるか判定せよ。

解法

LCM(C)がKの倍数なら条件を満たす。
LCM(C)を直接求めると多倍長が必要になってTLEするので、直接LCMを求めず、GCD(LCM(C),K)だけ順次計算していって最後にこれがKになるか判定すればよい。

int N,K;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	ll v=1;
	scanf("%d%d",&N,&K);
	FOR(i,N) {
		scanf("%d",&x);
		ll a=__gcd(x,K);
		ll b=__gcd(v,a);
		v=v*(a/b);
	}
	
	if(v==K) _P("Yes\n");
	else _P("No\n");
	
}

まとめ

意外にHackできた。