题意
黑板上有n个不同的数\(x_1,x_2,\cdot,x_n\)，你可以选择黑板上已有的两个数\(x,y\)，并将\(2x-y\)写在黑板上，问你通过一系列操作是否能写下数字k。
数据范围
\[2\leq n\leq 2\times 10^5 \] \[-10^{18}\leq k \leq 10^{18} \] \[-10^{18}\leq x_i\leq 10^{18} \]题解
- 首先明确:对于当前问题\((x_1,x_2,...x_n)[k]\)，对每一个数减去c，新问题\((x_1-c,x_2-c,...,x__n-c)[k-c]\)等价于原问题\((x_1,x_2,...x_n)[k]\)。
证明：
对于任意两个数\(x,y\)，可以得到\(2x-y\)，对于\(x-c,y-c\)，得到的新数为\(2(x-c)-(y-c)=2x-y-c\)。
对所有的数减去一个值c，之后继续操作得到的新数相当于原数进行操作得到的数减c。
即生成的所有数也减去了c，若减去c后能得到k-c，相当于原来的数能得到k。
之后的讨论中，我们将所有数减去\(x_1\)，问题转化为\((0,x_2,x_3,...x_n)[k-c]\)（这里的\(x_i\)为原来的\(x_i\)减去了\(x_1\))
2. 记\(g=gcd(x_2,x_3,...,x_n)\)，要能得到k，k一定满足\(g|k\)。
证明:
由于\(g=gcd(x_2,x_3,...,x_n)\),则g|\(x_i\)
若\(g|x,g|y\)，则\(g|2x-y\)，得证。
3.若k满足\(g|k\)，\((0,x_2,x_3,...,x_n)\)通过操作一定能得到k。
证明：（数学归纳法）
\(g=gcd(x_2,x_3,...,x_{n-1})\)
若\(n=2\)时，\(g_0=x_2\)，另一个数为0，可以得到任意倍数的\(g_0\)。
假设前n-1个数的最大公因数为\(g_0\)，且前n-1个数能得到\(sg_0\)（s为整数），由于0\(与\)x_n\(进行操作可以得到\)tx_n\(，根据裴蜀定理，一定存在整数s，t使得\)g_0s+x_nt=g\(。
所以若k满足\)g|k\(，\)(0,x_2,x_3,...,x_n)$通过操作一定能得到k。
裴蜀定理
\[ax+by=m \]方程有整数解当且仅当\(m\)为\(gcd(a,b)\)的倍数。
代码
/*************************************************************************
> File Name: 1.cpp
> Author: Knowledge_llz
> Mail: 925538513@qq.com
> Blog: https: https://www.cnblogs.com/Knowledge-Pig/
> Created Time: 2021/1/28 23:38:54
************************************************************************/
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define LL long long
#define pb push_back
#define fi first
#define se second
#define pr pair<int,int>
#define mk(a,b) make_pair(a,b)
using namespace std;
LL read(){
char x=getchar(); LL u=0,fg=0;
while(!isdigit(x)){ if(x=='-') fg=1; x=getchar(); }
while(isdigit(x)){ u=(u<<3)+(u<<1)+(x^48); x=getchar(); }
return fg?-u:u;
}
const int maxx=2e5+10;
LL n,k,a[maxx],d[maxx];
LL gcd(LL x,LL y){
return !y?x:gcd(y,x%y);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#endif
int T=read();
For(_,1,T){
n=read(); k=read(); a[1]=read();
k-=a[1];
For(i,2,n){
a[i]=read();
a[i]-=a[1];
}
LL g=a[2];
For(i,3,n) g=gcd(g,a[i]);
if(k%g==0) printf("YES\n");
else printf("NO\n");
}
return 0;
}