D - Nezzar and Board(思维+裴蜀定理)

https://codeforces.com/contest/1478/problem/D

题意:有n个数，可以进行一种操作得到2x−y， 原数不会消失，问能否得到k.

思路:

没思路硬模拟(或者看到这个多个数构成..感觉像裴蜀定理

2x−y 可以看做x+(x−y),即该数与两数之差的和。

用几组样例模拟一下，可以发现，无论进行多少次操作，始终都是ai​+∑{j,k}​(aj​−ak​)，也就是在若干组差值加上一个值。

这样的话就是要n^2枚举差值了。但是还有个性质。a2-a1已知,a3-a2已知，是可以线性组合成a3-a1的，也就是说只要O(n)，可以得到组成n^2所有差的原材料。

那么如果能被这(n-1)线性组合出来，那么其最终反应形态就是∑{j,k}​(aj​−ak​),只不过前面系数有0有其他值，各不相同。

于是就到了ai+∑{2~n}​(ai​−ai-1​)=K；

提前减去ai,转化∑{2~n}​(ai​−ai-1​)=K-ai;

前面的部分就是看gcd(左边一串)是否能被右边整除。（多个数的裴蜀定理嘛

然后最后可以On扫一下看有没有ai是满足答案的。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=2e5+100;
typedef long long LL;
inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL a[maxn];
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  LL t;cin>>t;
  while(t--){
    LL n,k;cin>>n>>k;
    for(LL i=1;i<=n;i++) cin>>a[i];
    LL gcd=0;
    for(LL j=1;j<=n;j++){
        gcd=__gcd(gcd,a[j]-a[1]);
    }
    bool flag=1;
    for(LL i=1;i<=n;i++){
        if((k-a[i])%gcd==0){
            flag=0;
            cout<<"YES"<<"\n";
            break;
        }
    }
    if(1==flag) cout<<"NO"<<"\n";
  }
return 0;
}