codeforces 1478D Nezzar and Board（裴蜀定理）_鼠蹊定理

题目链接在这里 ~~

题目大意

给一个数组和一个 k，数组内有 n 个数，可以进行无数次操作。每次选择两个数 x 和 y，得到一个新的数 2 * x - y，把这个数加入到数组里边。
问：是否可以得到数字 k 。

裴蜀定理

这里引用百度百科的解释：

裴蜀定理（或贝祖定理）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

接下来我们再引入 n个整数间的裴蜀定理

设a₁, a₂, a₃ … a_n 为n个整数，d 是它们的最大公约数，那么存在整数x₁ … x_n 使得 x₁ * a₁ + x₂ * a₂ + … x_n * a_n = d。
特别来说，如果a₁ … a_n互质（他们所有数的gcd = 1），那么存在整数x₁ … x_n 使得x₁ * a₁ + x₂ * a₂ + … x_n * a_n = 1。

（ 如果想不明白为什么，就不要想了，应用就OK ）
接下来，我们来讨论这个题。
我们可以进行的操作是选择（x ，y）然后得到 2 * x - y，我们对 2 * x - y 进行变形，得到 x + (x - y)。
也就是说看可以得到 num = a_x + x₁ * (a₁ - a₂) + x₂ * (a₂ - a₃) + … + x_n-1 * ( a_n-1 - a_n).
令 g = x₁ * (a₁ - a₂) + x₂ * (a₂ - a₃) + … + x_n-1 * ( a_n-1 - a_n)，那么根据 n个整数间的裴蜀定理 得，对 x₁ … x_n 进行不同的取值可以使得 g = k * gcd( (a₁ - a₂)，(a₂ - a₃) … ,( a_n-1 - a_n)).

所以我只需要判断 k - a₁ 是否为 g 的倍数就OK。

这里我们再来解释两个细节问题：

1. 只需要取相邻两项的差即可，不用取 a₁ - a_x (x为任意数)的差值。因为我们可以通过 (a₁ - a₂) + (a₂ - a₃) + … + (a_x-1 - a_x) 来得到 a₁ - a_x。
2. 只需要判断 k - a₁ 就OK，通过 a₁ + (a_i - a₁) 可以得到任意的 a_i 。

AC代码

#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define ll long long
#define chushi(a, b) memset(a, b, sizeof(a))
#define endl "\n"
const double eps = 1e-8;
const ll INF=0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxn = 2e5 + 5;
const int N=1005;
using namespace std;

ll a[maxn];
	
int main(){
	
	int ncase;
	cin >> ncase;
	while(ncase--){
		ll n, k;
		cin >> n >> k;
		for(int i = 1; i <= n; i++) cin >> a[i];
		ll g = a[2] - a[1];
		for(int i = 3; i <= n; i++) g = __gcd(g, a[i] - a[i-1]);
		if((k - a[1]) % g == 0) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	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