Codeforces 题解 —— Codeforces Round #698 (Div. 1) —— A. Nezzar and Board —— 裴蜀定理_codeforces round 698 (div. 1)

有时间刷个水题，防止抑郁。

题目相关

题目链接

Codeforces Round #698 (Div. 1)，A 题，https://codeforces.com/contest/1477/problem/A。

Problem Statement

$n$ distinct integers $x_1,x_2,\dots ,x_n$ are written on the board. Nezzar can perform the following operation multiple times.

• Select two integers $x,y$ (not necessarily distinct) on the board, and write down $2x-y$. Note that you don’t remove selected numbers.

Now, Nezzar wonders if it is possible to have his favorite number $k$ on the board after applying above operation multiple times.

Input

The first line contains a single integer $t$ ($1\le t\le 10^5$) — the number of test cases.
The first line of each test case contains two integers $n,k$ ($2\le n\le 2\cdot 10^5,-10^{18}\le k\le 10^{18}$).
The second line of each test case contains $n$ distinct integers $x_1,x_2,\dots ,x_n$ ($-10^{18}\le x_i\le 10^{18}$).
It is guaranteed that the sum of $n$ for all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, print “YES” on a single line if it is possible to have $k$ on the board. Otherwise, print “NO”.
You can print each letter in any case (upper or lower).

Example

Input

6
2 1
1 2
3 0
2 3 7
2 -1
31415926 27182818
2 1000000000000000000
1 1000000000000000000
2 -1000000000000000000
-1000000000000000000 123
6 80
-5 -20 13 -14 -2 -11
1
2
3
4
5
6
7
8
9
10
11
12
13

Output

YES
YES
NO
YES
YES
NO
1
2
3
4
5
6

Note

In the first test case, the number $1$ is already on the board.
In the second test case, Nezzar could perform the following operations to write down $k=0$ on the board:

• Select $x=3$ and $y=2$ and write down $4$ on the board.
• Select $x=4$ and $y=7$ and write down $1$ on the board.
• Select $x=1$ and $y=2$ and write down 0 on the board.

In the third test case, it is impossible to have the number $k=-1$ on the board.

题解报告

题目翻译

黑板上写着 $n$ 个不同的整数 $x_1,x_2,\dots ,x_n$。Nezzar 可以进行以下操作任意次：

• 选择两个整数 $x$ 和 $y$，这两个整数不需要不同，计算出 $2x-y$ 的结果。注意你不需要删除已经选中的数据。

现在，Nezzar 想知道，经过任意次操作后，是否可以获得他最喜欢的数字 $k$。

题目分析

本题又是一个最大公约数（GCD）问题。就是求数列 $x_1,x_2,\dots ,x_n$ 的最大公约数，关于求数列最大公约数的分析，请参考 https://blog.csdn.net/justidle/article/details/112252780。
根据题目的要求，我们从数列 $x_1,x_2,\dots ,x_n$ 中选出两个数 $x$ 和 $y$，进行 $2x-y$ 的操作，最终得到的数要为 $k$。也就是意味着，经过了若干次（比如 $m$ 次）操作，我们将得到 $k$。也就是意味着数列的 $x_1,x_2,\dots ,x_n$ 的最大公约数 $ans-x_1$ 必须是 $k$ 的倍数。

进一步解释

有人问为什么这样想。
首先，考虑知识点。看到题目，应该可以联想到到考点就是数列的 GCD。
其次，这题就是裴蜀定理。根据题目 $g|x,g|y⟹g|(2x-y)$。下面我们只需要证明如果 $\forall x$ 可以被 $g$ 整除，我们就可以在黑板上写出 $x$。

裴蜀定理

在数论中，裴蜀定理（Bézout’s Theorem）是一个关于最大公约数（或最大公约式）的定理，裴蜀定理得名于法国数学家艾蒂安·裴蜀。裴蜀定理说明了对任何整数 $a$、$b$ 和它们的最大公约数 $d$ ，关于未知数 $x$ 以及 $y$ 的线性的丢番图方程（称为裴蜀等式）。具体定理描述如下：
设 $a_1,a_2,..,a_n$ 为 $n$ 个整数，$d$ 是它们的最大公约数，那么存在整数 $x_1,...,x_n$ 使得 $x_1\ast a_1+x_2\ast a_2+...x_n\ast a_n=d$。
特别来说，如果 $a_1,a_2,..,a_n$ 互质（不是两两互质），那么存在整数 $x_1,...,x_n$ 使得 $x_1\ast a_1+x_2\ast a_2+...x_n\ast a_n=1$。
下面我们回到题目，题目的操作是 $2x-y$，我们来推导一下操作的过程：
1、第一次取 $x$ 和 $y$。这样我们得到 $2x-y$；
2、第二次取 $p$ 和 $q$。结合第一次操作，我们可以得到 $2\ast (2x-y)-(2q-p)$；
3、以此类推。
通过观察，可以发现，最终的系数和是 $2\ast 1-1$ 这样的形式。也就是说，经过若干次操作，我们将最终得到 $k-a_i$ 这样的值。这就是裴蜀定理。

CF 官方解释

AC 参考代码

#include <bits/stdc++.h>

using namespace std;

//如果提交到OJ，不要定义 __LOCAL
//#define __LOCAL
typedef long long ll;
const int MAXN=2e5+4;
ll a[MAXN];

int main() {
#ifndef __LOCAL
	//这部分代码需要提交到OJ，本地调试不使用
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	//cout.tie(0);
#endif
	int t;
    scanf("%d", &t);
	//cin>>t;
	while (t--) {
		ll n,k;
        scanf("%lld %lld", &n, &k);
		//cin>>n>>k;

		for (int i=1; i<=n; i++) {
            scanf("%lld", &a[i]);
			//cin>>a[i];
		}

		//求gcd
		ll ans=0;
		for (int i=1; i<n; i++) {
			ans = __gcd(ans, a[i+1]-a[i]);
		}

		//判断关系
		if ((k-a[1])%ans == 0) {
            printf("YES\n");
			//cout<<"YES\n";
		} else {
            printf("NO\n");
			//cout<<"NO\n";
		}
	}

#ifdef __LOCAL
	//这部分代码不需要提交到OJ，本地调试使用
	system("pause");
#endif
	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

124 ms 是用 scanf 和 printf 的时间，218 ms 是用 cin 和 cout 快读的时间。

时间复杂度

$O(N)$。

空间复杂度

$O(N)$。