ArabellaCPC 2019 Meeting Bahosain 最大公约数

Meeting Bahosain

给你一个数组a和一个数组b，你可以让数组a中的数 +/- 数组b中的任一个数。目标使a数组中数相等。

可以将a[n]的值转化为a[n-1]再转化为a[n-2]，……，最后使所有数都等于a[0]，那么就是对于所有a[i] - a[i-1]都能由b表示出来，就输出YES

设对于所有i ，x=a[i] - a[i-1] , 那么x=k1*b1 + k2*b2 +k3*b3 + k4*b4 ……，ki是任意整数（每次只能加减bi），可以发现只要x % gcd(b1 b2....bn) ==0 ,那么该方程一定成立。例如：3=2*k1+4*k2 -->3/2=k1+2*k2 ,方程无解。对于每个x % gcd(b) == 0 ,那么相当于gcd（x）%gcd(b)

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
int n, m;
int a[N], b[N];
int gcd1, gcd2;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n ; i++){
		cin >> a[i];
		if(!i) gcd1 = a[i];
		else if(abs(a[i] - a[i-1])){
			gcd1 = __gcd(gcd1, abs(a[i] - a[i-1]));
		}
	}
	for(int i = 0; i < m ; i++){
		cin >> b[i];
		if(!i) gcd2 = b[i];
		else gcd2=__gcd(gcd2, b[i]);
	}
	
	if(gcd1%gcd2 && n != 1)cout << "No\n";
	else cout << "Yes\n";
	return 0;
}