Codeforces #698 Div1 : A. Nezzar and Board

ようやく2021/2…。
https://codeforces.com/contest/1477/problem/A

問題

整数集合Aが与えられる。
Aの2要素x,yを選び、Aに2x-yを加えるという作業を繰り返したとき、A中に整数Kを登場させることはできるか判定せよ。

解法

x＜yとすると、xとyから生成できるのは整数nを用いてx+n(y-x)の形の値である。
よって、Aから生成できるのは、Aのうち2要素の差分の絶対値のGCDをgとすると、x∈Aに対しx+ngで表せる整数である。

int T;
int N;
ll K;
ll X[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		ll g=0;
		FOR(i,N) {
			cin>>X[i];
			if(i) g=__gcd(g,abs(X[i]-X[i-1]));
		}
		
		K-=X[0];
		if(abs(K)%g==0) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
		
	}
}

まとめ

これは本番も割とあっさり解いてるな。