Codeforces #691 Div1 A. Row GCD

2完なのにレート微減で済んだ回。
https://codeforces.com/contest/1458/problem/A

問題

2つの整数列A,Bが与えられる。
Bの各値B[j]に対し、gcd(A[0]+B[j],A[1]+B[j],...)を求めよ。

解法

互除法のアルゴリズムを考えると、求める値は
gcd(A[0]+B[j], A[1]-A[0], A[2]-A[1], ...)となる。
そこで、あらかじめ第2項目以降のGCDを求めておけば、Bの要素毎にGCDを追加で1回計算するだけで良くなる。

int N,M;
ll A[202020],B[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	FOR(i,M) cin>>B[i];
	sort(A,A+N);
	ll g=0;
	FOR(i,N-1) g=__gcd(g,A[i+1]-A[i]);
	FOR(i,M) cout<<__gcd(B[i]+A[0],g)<<" ";
	cout<<endl;
}

まとめ

まぁこれは簡単。