A. Nezzar and Board - 裴蜀定理 -数论 -gcd_gcd=__gcd(gcd,abs(a[i]-a[i-1]));

Problem - A - Codeforces

A. Nezzar and Board

time limit per test

2 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

nn distinct integers x1,x2,…,xnx1,x2,…,xn are written on the board. Nezzar can perform the following operation multiple times.

• Select two integers x,yx,y (not necessarily distinct) on the board, and write down 2x−y2x−y. Note that you don't remove selected numbers.

Now, Nezzar wonders if it is possible to have his favorite number kk on the board after applying above operation multiple times.

Input

The first line contains a single integer tt (1≤t≤1051≤t≤105) — the number of test cases.

The first line of each test case contains two integers n,kn,k (2≤n≤2⋅1052≤n≤2⋅105, −1018≤k≤1018−1018≤k≤1018).

The second line of each test case contains nn distinct integers x1,x2,…,xnx1,x2,…,xn (−1018≤xi≤1018−1018≤xi≤1018).

It is guaranteed that the sum of nn for all test cases does not exceed 2⋅1052⋅105.

Output

For each test case, print "YES" on a single line if it is possible to have kk on the board. Otherwise, print "NO".

You can print each letter in any case (upper or lower).

Example

input

Copy

6
2 1
1 2
3 0
2 3 7
2 -1
31415926 27182818
2 1000000000000000000
1 1000000000000000000
2 -1000000000000000000
-1000000000000000000 123
6 80
-5 -20 13 -14 -2 -11

output

Copy

YES
YES
NO
YES
YES
NO

Note

In the first test case, the number 11 is already on the board.

In the second test case, Nezzar could perform the following operations to write down k=0k=0 on the board:

• Select x=3x=3 and y=2y=2 and write down 44 on the board.
• Select x=4x=4 and y=7y=7 and write down 11 on the board.
• Select x=1x=1 and y=2y=2 and write down 00 on the board.

In the third test case, it is impossible to have the number k=−1k=−1 on the board.

=========================================================================

网上不乏各种caodan题解，讲的稀里糊涂，其实就是没做出来看别的题解一知半解之后瞎糊弄。

这里先借助 2x-y  这一条件 先手玩一下样例 

a1 a2 a3 a4 a5

得a6= 2a1-a2 = a1+ (a1-a2)

得a7= 2a6-a3 = 2(2a1-a2)-a3 = 4a1-2a2-a3 = a1 + 2(a1-a2) - (a1-a3)

得a8 = 2a5- a7 = 2a5-a1-2(a1-a2)+(a1-a3)  =a5 +(a5-a1) -2(a1-a2) +(a1-a3)

.....

手玩几次不难发现，我们最终新产生的，就是原数组的ai  + 若干 (aj-ak),  jk为原数组的下标

对于ai 来说，我们有n中   aj-ak就有n^2种，那么最终答案一定是其中n个之一

 a1+  k1 (a1-a1)+k2(a1-a2)+..... +kn*n (an-an)    

 a2+ k1 (a1-a1)+k2(a1-a2)+..... +kn*n (an-an)   

....

an+k1 (a1-a1)+k2(a1-a2)+..... +kn*n (an-an)    

我们先不考虑化简什么的，至少目前获得了一个巨暴力的方法，那就是对K-ai ,看能不能被 k1 (a1-a1)+k2(a1-a2)+..... +kn*n (an-an)   表示， 这时用到裴蜀定理，也即是K-ai 是，这n^2个数字gcd的倍数即可。

接下来才是本题关键，如何化简?

将数组进行排序

 我们只需要 a2-a1  a3-a2  a4-a3  a6-a4 a7-a6就能表示出来全部六个数字两两相减的结果！

那么就好办咯，既然n^2的结果等价于n-1个的结果，那就排个序，再跑一个暴力就是了

不需要任何复杂的推理，至于网上那种纯数学推理，一个是非常不严谨，二个是几乎很难考证正确性。

#include <bits/stdc++.h>
 
using namespace std;
typedef long long int ll;
 
ll a[200000+10];
int main()
{
 
  int t;
  cin>>t;
 
  while(t--)
  {
      ll n,k;
      cin>>n>>k;
 
      for(int i=1;i<=n;i++)
      {
          cin>>a[i];
      }
 
      sort(a+1,a+1+n);
 
      ll gcd=0;
 
      for(int i=2;i<=n;i++)
      {
          gcd=__gcd(gcd,a[i]-a[i-1]);
      }
 
      int ans=0;
      for(int i=1;i<=n;i++)
      {
          if((k-a[i])%gcd==0)
          {
              ans=1;
          }
      }
 
      if(ans)
      {
          cout<<"YES"<<endl;
      }
      else
      {
          cout<<"No"<<endl;
      }
  }
 
    return 0;
}