CodeForces - 1477A - Nezzar and Board（数论）_h. nezzar and board

Nezzar and Board

题意

对 一个大小为 $n$ 的整数集合 进行操作 每次可以选取两个数 $x,y$ 得到 $2x-y$ 加入这个集合

问 经过无限次这样的操作之后 能否得到 $k$

思路

假设一次操作后得到 $2x-y$ 另一次操作后得到 $2p-q$

那么这两个新得到的数再进行操作可以得到 $2\ast (2x-y)-(2p-q)$ 可以得到一个规律 ：每次操作得到的式子 系数都为1 那么怎样才能得到一个系数为1的式子呢？

只需要构造一个系数为0的式子 然后再随便加一个数即可 设这个数为$a_x$ 例如 $(a_i-a_j)+a_x$

所有的系数为0的式子为 $p_1(a_1-a_1)+p_2(a_1-a_2)+\cdots +p_n(a_n-a_1)+p_{n+1}(a_2-a_1)+\cdots +p_{n\ast n}(a_n-a_n)$ 但是这样求出所有的式子的时间复杂度是 $O(n^2)$ 的 显然会TLE

但是我们知道 任意一个 $a_i-a_j$(假设 $j<i$) 都可以用 $(a_i-a_{i-1})-(a_{i-1}-a_{i-2})-\cdots -(a_{i-x}-a_j)$ 表示

所以只要求出所有 $a_i-a_{i-1}$ 就可以线性表示出上面的式子即：

$q_1(a_2-a_1)+q_2(a_3-a_2)+\cdots +q_{n-1}(a_n-a_{n-1})=p_1(a_1-a_1)+p_2(a_1-a_2)+\cdots +p_n(a_n-a_1)+p_{n+1}(a_2-a_1)+\cdots +p_{n\ast n}(a_n-a_n)$ 其中 $p、q$ 均为系数

此时问题转变成 $q_1(a_2-a_1)+q_2(a_3-a_2)+\cdots +q_{n-1}(a_n-a_{n-1})+a_x=k$ $(1\le x\le n)$是否成立

即$q_1(a_2-a_1) + q_2(a_3-a_2) + \dots + q_{n-1}(a_n-a_{n-1}) = k -a_x $ $(1\le x\le n)$

由裴蜀定理可知 此式成立的条件为 $gcd((a_2-a_1),(a_3-a_2),\dots ,(a_n-a_{n-1}))$ 能够整除 $k-a_x$

那么 只要先求出 所有相邻数差的 $gcd$ 后 依次对每个$a_x$判断即可

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;

typedef  long long LL;
typedef pair<int, int>PII;
inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
const int N = 200010;

LL n, k;
LL a[N];


void solve() {
	cin >> n >> k;
	LL res = 0;

	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		//res = gcd(res, a[i] - a[i - 1]);
	}

	for (int i = 2; i <= n; ++i)
		res = gcd(res, a[i] - a[i - 1]);

	for (int i = 1; i <= n; ++i) {
		if ((k - a[i]) % res == 0) {
			puts("YES");
			return;
		}
	}
	puts("NO");
}

int main() {
	int t; cin >> t;
	while (t--)
		solve();

	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