codeforces1478D Nezzar and Board_codeforces 1478 d

题目：

在黑板上有$n$个不同数$x_{1...n}$，每次可以选择两个数$x,y$，将$2x-y$写在黑板上（$x,y$两数不擦除，还可以再用），问给定的数$k$能不能出现在黑板上。
$(2\le n\le 2\times 10^5,-10^{18}\le k,x_i\le 10^{18})$

题解：

可以发现$2x-y$可以写成$x+(x-y)$，猜想是不是所有在黑板上的数都可以表示成$x_i+{\sum }_{i=1}^n{\sum }_{j=1}^n{k}_{i,j}(x_i-x_j)$的形式。可以用归纳法证明，显然初始的$x_{1...n}$都是满足的，假设目前黑板上的数都可以写成这种形式，进行一次操作，选取$x_i+{\sum }_{i=1}^n{\sum }_{j=1}^n{a}_{i,j}(x_i-x_j),x_j+{\sum }_{i=1}^n{\sum }_{j=1}^n{b}_{i,j}(x_i-x_j)$，得到$x_i+(x_i-x_j)+{\sum }_{i=1}^n{\sum }_{j=1}^n(2a_{i,j}-b_{i,j})(x_i-x_j)$，显然还是满足这个形式，所以黑板上所有的数都满足这种形式。且所有形如$x_i+{\sum }_{i=1}^n{\sum }_{j=1}^n{k}_{i,j}(x_i-x_j)$的数都可以出现在黑板上，这个证明暂且不会。
那么我们就要看$k-x_i$可不可以是一个$x_i-x_j$的线性组合了，这个可以用裴蜀定理来判断，但是$x_i-x_j$有$O(n^2)$个，不能通过此题。我们发现所有的$x_i-x_j$都可以表示成$x_i-x_{i-1}$的线性组合，$x_i$可以表示为$x_1+{\sum }_{j=1}^i(x_j-x_{j-1})$，所以黑板上的数也可以表示为$x_1+{\sum }_{i=2}^n{k}_i(x_i-x_{i-1})$，问题就变成判断${\sum }_{i=2}^n{k}_i(x_i-x_{i-1})=k-x_1$是否有解，用裴蜀定理判断，令$g=gcd(|x_2-x_1|,|x_3-x_2|,...,|x_n-x_{n-1}|)$，判断$|k-x1|$是否能被$g$整除即可。

复杂度：$O(nlog10^{18})$

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<bitset>
#include<sstream>
#include<ctime>
//#include<chrono>
//#include<random>
//#include<unordered_map>
using namespace std;

#define ll long long
#define ls o<<1
#define rs o<<1|1
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
const double pi=acos(-1.0);
const double eps=1e-6;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const int maxn=2e5+5;
ll read(){
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int t,n;
ll k;
ll x[maxn];
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int main(void){
	// freopen("in.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d%lld",&n,&k);
		for(int i=1;i<=n;i++){
			scanf("%lld",&x[i]);
		}
		ll g=x[2]-x[1];
		for(int i=3;i<=n;i++){
			g=gcd(g,abs(x[i]-x[i-1]));
		}
		if(abs(k-x[1])%g==0){
			puts("YES");
		}
		else{
			puts("NO");
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69