codeforces 698 Div1 A Nezzar and Board (构造+数论)_codeforces nezzar and board

题目链接：https://codeforces.com/contest/1477/problem/A

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.

 

题意：黑板上又n个整数x1,x2......xn。每次操作你可以选择两个数字(x,y)，把（2x-y）写到黑板上。问数字K能否写到黑板上。

题解：解决这个问题首先需要了解数论知识裴蜀定理

定理

在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性丢番图方程（称为裴蜀等式）：

ax + by = m

有解当且仅当m是d的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解x、y都称为裴蜀数，可用辗转相除法求得。

n个整数间的裴蜀定理

编辑

设a1,a2,a3......an为n个整数，d是它们的最大公约数，那么存在整数x1......xn使得x1*a1+x2*a2+...xn*an=d。

特别来说，如果a1...an互质（不是两两互质），那么存在整数x1......xn使得x1*a1+x2*a2+...xn*an=1。证法类似两个数的情况。

了解了裴蜀定理，我们再继续进行构造，本题我们观察到，当存在数字0时，比如两个数字（0，g），一次操作我们可以得到（0，g，2g），继续操作我们可以得到（0，g，2g，3g.....）。我们可以写出所有g的整数倍的数。

我们假设x1=0，那么我们可以写出所有数字k(Xi) (2<=i<=n)，设gcd(x2,x3,....xn)=d，显然k一定为d的整数倍，那么是否所有d的整数倍都能写出来呢，我们可以通过归纳法来证明。

当n==2时，由于x1=0，所以gcd（x1，x2）=x2，有上面的推理我们可知所有x2的整数倍都可以写出来

当n>2时，设d0=gcd(x2,x3,....xn-1)，因为d=gcd(g0,xn)，由裴蜀定理可知 s*g0+t*xn=d 一定有解，由于g0可以写出来，所有g0的整数倍也可以写出来，所有xn的倍数也可以写出来，那么d我们也可以写出来，那么所有d的整数倍我们也可以写出来。

由此我们就离解决问题非常近了，但本题中，x1并不一定为0，该怎么办呢？

我们可以构造一个数列（x1-x1,x2-x1,x3-x1,.......xn-x1）

由于2（xi-x1）-（xj-x1）=2xi-xj-x1，本数列的所有解，加上x1就是原数列的所有解。

本题Xi可能为负数，所以我们先将数列按从小到大排序，求出构造数列的最大公约数g，那么，所有g的倍数加上x1，就是k的解。

本题的构造，实在是太巧妙！！！

代码如下：

#include<bits/stdc++.h>
 
using namespace std;
const int nn =210000;
const int inff = 0x3fffffff;
const double eps = 1e-8;
typedef long long LL;
const double pi = acos(-1.0);
const LL mod = (479 << 21) + 1;
LL gcd(LL x,LL y)
{
    if(y==0)
    {
        return x;
    }
    return gcd(y,x%y);
}
LL a[nn];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        LL n,k;
        scanf("%lld%lld",&n,&k);
        for(int i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
        }
        sort(a,a+n);
        LL d=0;
        for(int i=1;i<n;i++)
        {
            d = gcd(d,a[i]-a[0]);
        }
        if((k-a[0])%d==0)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}