D. Nezzar and Board

題目鏈接：

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

Description

Input

Output

題意

給一個數列， a 1 a_1 a1?, a 2 a_2 a2?, a 3 a_3 a3?… a n a_n an? , 每一次操作定義為，從已有的數字中隨意選一個數字作為x，再選一個數字作為y，兩個數字可以相同，然后向數列中加入2*x - y 這個數字，選中的數字仍然在數列中，

可以操作任意次，問是否能湊出k，

題解：

首先考慮最終組成的運算式的形式,當只進行一次操作時，結果一定是 2 ? x ? y 2*x- y 2?x?y這樣的形式，當進行兩次操作，那么一定是 2 ? ( 2 ? x ? y ) ? ( 2 ? p ? q ) 2 *(2*x - y) - (2 * p -q ) 2?(2?x?y)?(2?p?q) 這樣的形式，所以觀察系數和可以發現，系數和最終一定是 2 * (1) - 1 這樣的形式，由于每次都會得到一個系數和為1的運算式，所以最終的運算式系數和一定為1.反過來想也就是，用這個方法可以湊出所有系數為1的運算式，

然后怎么才能湊出所有系數為1的運算式呢，也就是湊出所有系數為0的運算式然后再隨便加一個數字即可，所以我們需要所有的 a i ? a j a_i - a_j ai??aj? 進行組合，這樣就可以湊出所有系數為0的運算式，但是組合方式是 n 2 n^2 n2的，我們又可以通過把每個值變成 a i ? a i ? 1 a_i - a_{i-1} ai??ai?1?的形式，這樣我們就能通過n - 1個運算式之間的運算湊出 n 2 n^2 n2種系數為0的 a i ? a j a_i - a_j ai??aj?形式的表達，

最終，我們就得到了n-1 個值，我們要看這n - 1個值通過任意組合能否得到一個等于 k - a i a_i ai? 這樣的值，這就是裴蜀定理，

所以我們只需要算出n-1個數的gcd，看下是不是 k ? a [ i ] （ 1 ≤ i ≤ n ） k - a[i]（1 \le i \le n） k?a[i]（1≤i≤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;
}