Nezzar and Board(多个数的裴蜀定理)

Nezzar and Board
题意：给出数组 a ，每次操作 可以 选任意两个数x，y 。数组中加入 2x-y。求是否可以变成k。

思路：经过模拟发现 变化的数可以写成 ai+∑(aj-ak)。aj-ak=(aj-ai)+(ai-ak) … …ai可以写成 ai=(ai-a(i-1))+a(i-1)
最后可以写成 a1+∑ fi (ai-a(i-1)) 即求这个式子是否等于 k
即 f1(a2-a1)+f2(a3-a2)+f3(a4-a3)+……+=k-a1
令g = g c d ( [ ai − a (i − 1) ] ) , i ∈ [ 2 , n ]
若 (k-a1)%g==0 则 有解 (裴蜀定理)

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int inf=2e18+100;
const int maxn=2e5+100;
int a[maxn];
int n,k;
signed main()
{
	IOS
	int tt;
	cin>>tt;
	while(tt--)
	{
		cin>>n>>k;
		bool fg=0;
		int gcd=0; 
		for(int i=1; i<=n; i++)
		{
			cin>>a[i];
			if(a[i]==k)fg=1;
			if(i>=2)gcd=__gcd(gcd,a[i]-a[i-1]);
		}
		if((k-a[1])%gcd==0)fg=1;
		if(fg)cout<<"YES"<<"\n";
		else cout<<"NO"<<"\n";
	}
}
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