Codeforces Round #698 (Div. 2) D. Nezzar and Board（数论，贝祖定理）_cf #698 nezzar and board

题目链接
自己太菜，这道题目好多篇题解，但是都弄得不是太明白。官方英文题解的又看的不太懂，最后发现了这篇证明和这篇题解，才慢慢弄明白，也让我对贝祖定理有了新的认识。

#include<bits/stdc++.h>
using namespace std;

#define Min(a,b,c)  min(a,min(b,c))
#define Max(a,b,c)  max(a,max(b,c))
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const double pi = 3.141592653589793;
const double eps = 1e-8;

ll x[200020];

ll gcd(ll a, ll b)
{
	while(b)
	{
		ll r = a % b;
		a = b;
		b = r;
	}
	return a;
}


int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--)
	{
		ll n, k;
		cin >> n >> k;
		for (ll i = 1; i <= n; i++)
		{
			cin >> x[i];
			if (i > 1)
			    x[i] -= x[1];
		}
		k -= x[1];
		
		ll g = 0;
		for (ll i = 2; i <= n; i++)
			g = gcd(g, x[i]);

		if (k % g == 0)
		    cout << "YES" << endl;
		else
		    cout << "NO" << endl;
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

时间复杂度不超过O(N*logX)