Codeforces Round #698 (Div. 2) D. Nezzar and Board（找规律+裴蜀定理）_y0ull2丫z

传送门

题目大意

给出一个$n$个数，每次可以从序列中任选两个数$x,y$，然后将$2x-y$添加进序列。给定$k$问它能否被表示出来。

解题思路

假设有三个数$x,y,z$，首先我们选出$x,y$构成$2x-y=x+x-y$，选出$y,z$构成$2z-y=z+z-y$，然后对这两个新得到的数，我们再做一次得到$2(2x-y)-(2z-y)=(x+x-y)+(x+x-y)-(z+z-y)=x+2(x-y)+(y-z)+(x-z)$，然后我们还可以找到很多种这样的数，可以发现，每种数都可以被表示为$a_i+{\sum }_{j,k}(a_j-a_k)$，也就是说会是$a_i$和其中若干个数对之差的线性组合。

联系到$n$个数的裴蜀定理，对于$a_1,a_2,...,a_n$，我们一定可以找到$a_1\ast x_1+a_2\ast x_2+...+a_n\ast x_n=gcd(a_1,a_2,...,a_n)$，那么显然对于给定的$k$，我们只需要看 ( k − a i ) % g c d ( { a i } ) (k-a_i)\%gcd(\{a_i\}) (k−ai​)%gcd({ai​})是否为零。

对于本题的就是对上面说的$a_j-a_k$求gcd，但是肯定不能求出所有的任意两数之差，我们发现只需要计算出相邻两数之差，线性组合后就相当于求出了所有，而$a_i$也都可以被表示出来，因此我们只需要从序列中任选一个数$a_i$判断$(k-a_i)\%gcd$是否为零。

//
// Created by Happig on 2021/1/30.
//
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;
#define ENDL "\n"
#define lowbit(x) (x & (-x))
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double dinf = 1e300;
const ll INF = 1e18;
const int Mod = 998244353;
const int maxn = 2e5 + 10;

ll a[maxn];

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t, n;
    ll k;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        for (int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + 1 + n);
        ll g = 0;
        for (int i = 2; i <= n; i++) {
            g = gcd(g, a[i] - a[i - 1]);
        }
        //cout << g << ENDL;
        if ((k - a[1]) % 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