codeforces 1477C. Nezzar and Nice Beatmap（裴蜀定理）_给定n个数的数组h,给两个数x y

本人的第一篇博客。写的不太好还请见谅w
链接: https://codeforces.com/problemset/problem/1477/C.

---

1.题意

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

2.思路

首先肯定需要化简题目给的表达式，将2x-y简化成x+（x-y）,所以最后的答案就是数列中的某一个数加上某两个数之差，可以使用裴蜀定理

对所有元素求一个gcd。判断 (k-a[1])%gcd 是否等于0就行了。

3.代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	int t;
	cin>>t;
	ll a[1000009];
	while(t--)
	{
		ll n,m,ans=0;
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		ans=a[2]-a[1];
		for(int i=2;i<=n;i++)
		{
		  ans=__gcd(a[i]-a[i-1],ans);	
		}	
		//可以通过任意次操作使得m=任意一个数加上任意两个数的差。
		// 所以这里的ans放下了所有数字差的gcd
		if((m-a[1])%ans==0)
		cout<<"YES"<<endl;
		else
		cout<<"NO"<<endl;
	}
}
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