鄙人不才,此中鄙陋甚多,望海涵!!!
题目大意:利用2*ai-aj
这个式子进行可以进行任意多次变化,新变化后得到的数字还可以加入数组中再参与变化,对于2个数字x和y其实我们能变化出的数字是2个等差序列,(2*x-y==x+x-y)
1. x+x-y x+2*(x-y) x+3*(x-y) x+4*(x-y) x+5*(x-y)....
2. y+y-x y+2*(y-x) y+3*(y-x) y+4*(y-x) y+5*(y-x)....
得到了这个规律以后我们就会想到要让这个差值尽可能的小,那样我们组成的数就多了,每2个数可以组成这样2个等差数列,新组成的等差数列也可能得到更小的差,而这里有一个数学定理(我也不知道叫什么),2个无限等差数列合成后,最小差值就是2个公差的gcd,这样的话我们就去找尽量可能小的差(排序求相邻)然后再求出他们的gcd就可!
C++Code
#include<iostream>
#include<algorithm>
#include<cmath>
#define int long long
using namespace std;
const int N=2e5+10;
int n,k;
int a[N];
int gcd(int a,int b)
{
return b ? gcd(b,a%b) : a;
}
signed main()
{
int T;
cin>>T;
while(T--)
{
scanf("%lld%lld",&n,&k);
for(int i=0;i<n;i++) scanf("%lld",&a[i]);
sort(a,a+n);
int d=a[1]-a[0];
for(int i=2;i<n;i++) d=gcd(d,a[i]-a[i-1]);
bool suc=false;
for(int i=0;i<n;i++)
{
if(abs(k-a[i])%d==0)
{
suc=true;
break;
}
}
if(suc) puts("YES");
else puts("NO");
}
}