Codeforces Round #698 (Div. 2) D. 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?x?y$这样的形式，当进行两次操作，那么一定是 $2?(2?x?y)?(2?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;
}