D. Nezzar and Board (裴蜀定理&gcd)_h. nezzar and board

D. Nezzar and Board (裴蜀定理&gcd)

---

题意

​ 给定$n$个不同的数，每次操作可以选择两个数$x,y$ ($x,y$可以相同)新增一个数$2x-y$。给定$k$，问是否能在若干次操作后得到$k$。

---

思路

​ 最后答案的形式肯定是：$2x-y=x+(x-y)=k$，即一个数加上(它与另一个数之差)的和组成，答案的形式是$a_i+\sum _{j,k}(a_j-a_k)$。考虑用裴蜀定理，

$\sum _{j,k}(a_j-a_k)=\sum _{i=2}^n{f}_i(a_i-a_{i-1}),f_i$为对应的系数。

令$g=gcd([a_i-a_{i-1}]),i\in [2,n]$

由裴蜀定理可知：$\sum _{i=2}^n{f}_i(a_i-a_{i-1})\%g=0$。

因此我们只需判断$(k-a_i)\%g=0$。

而$a_i,i\in [2,n]$都可以由$a_1+\sum (a_j-a_{j-1})$得到。

所以我们只需判断$(k-a_1)\%g=0$即可。

---

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int t,n;
ll k,a[N];
int main(){
	scanf("%d",&t);while(t--){
		ll x,g=0;
		scanf("%d%lld",&n,&k);
		for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
		for(int i=2;i<=n;i++) g=__gcd(g,a[i]-a[i-1]);
		puts((k-a[1])%g==0?"YES":"NO");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21