Solution -「CF 1477A」Nezzar and Board

Description

$ n $ distinct integers $ x_1,x_2,\ldots,x_n $ are written on the board. Nezzar can perform the following operation multiple times.

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

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

Solution

Let us onsider how to express all the number we can express.
Since $2x-y=x+(x-y)$, the expression is $x_{i}+\sum_{j,k}x_{j}-x{k}$.
Since $x_{i}=x_{1}+(x_{1}-(x_{1}+(x_{1}-x_{i})))$, the expression could be written as $x_{1}+\sum_{i}x_{i}-x_{1}$, which means the answer exists where $\sum_{i}x_{i}-x_{1}=K-x_{1}$ has solutions.
Beout's identity works.

#include<bits/stdc++.h>
typedef long long ll;
#define sf(x) scanf("%d",&x)
#define ssf(x) scanf("%lld",&x)
int main()
{
    int T,n;
    ll k;
    sf(T);
    while(T-->0)
    {
        sf(n),ssf(k);
        ll g=0,x1,x;
        ssf(x1);
        for(int i=2;i<=n;++i)    ssf(x),g=std::__gcd(x-x1,g);
        puts((k-x1)%g==0?"YES":"NO");
    }
    return 0;
}