Codeforces Round #698 (Div. 2) D. Nezzar and Board_1477a. nezzar and board

D. Nezzar and Board

题目链接：

http://codeforces.com/contest/1478/problem/D

Description

Input

Output

题意

给一个数列，$a_1$,$a_2$,$a_3$…$a_n$ , 每一次操作定义为，从已有的数字中随意选一个数字作为x，再选一个数字作为y，两个数字可以相同，然后向数列中加入2*x - y 这个数字，选中的数字仍然在数列中。

可以操作任意次，问是否能凑出k。

题解：

首先考虑最终组成的表达式的形式,当只进行一次操作时，结果一定是$2\ast x-y$这样的形式，当进行两次操作，那么一定是 $2\ast (2\ast x-y)-(2\ast p-q)$ 这样的形式，所以观察系数和可以发现，系数和最终一定是 2 * (1) - 1 这样的形式，由于每次都会得到一个系数和为1的表达式，所以最终的表达式系数和一定为1.反过来想也就是，用这个方法可以凑出所有系数为1的表达式。

然后怎么才能凑出所有系数为1的表达式呢，也就是凑出所有系数为0的表达式然后再随便加一个数字即可，所以我们需要所有的$a_i-a_j$ 进行组合，这样就可以凑出所有系数为0的表达式，但是组合方式是$n^2$的，我们又可以通过把每个值变成$a_i-a_{i-1}$的形式，这样我们就能通过n - 1个表达式之间的运算凑出$n^2$种系数为0的 $a_i-a_j$形式的表达。

最终，我们就得到了n-1 个值，我们要看这n - 1个值通过任意组合能否得到一个等于 k - $a_i$ 这样的值。这就是裴蜀定理。

所以我们只需要算出n-1个数的gcd，看下是不是$k-a[i]（1\le i\le n）$的因子即可。

代码

#include <random>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
long long a[maxn];
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        long long k;
        cin >> n >> k;
        long long gcd = 0;
        map<long long,int> mp;
        cin >> a[1];
        mp[a[1]] = 1;
        for (int i = 2; i <= n; i++) {
            cin >> a[i];
            mp[a[i]] = 1;
            gcd = __gcd(gcd, (a[i]-a[i-1]));
        }
        int flag = 0;
        for (int i = 1; i <= n; i++) {
            if ((k - a[i]) % gcd ==0) {
                flag = 1;
            }
        }
        if (flag) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }

    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