Codeforces Round698 div2题解_输入一个数 ,请构造一个长度为 的排列,使得其中正好有 对相邻的数gcd(最大公约数)

Codeforces Round698 div2题解

A Nezzar and Colorful Balls

（这题我就不给翻译了吧）

求众数的出现次数即可

B Nezzar and Lucky Number

给定数$d(1\le d\le 9)$，如果一个数的十进制表示中的某一位为$d$，则这个数是“幸运数”。给定$q(1\le q\le 10^4)$个数$a_1,a_2,a_3,...,a_q(1\le a_i\le 10^9)$，对其中的每一个数，判断是否可以表示成一个或多个幸运数的和。

首先给出结论：如果$a_i$大于$10d$，那么$a_i$一定可以表示成幸运数的和。（我知道的最紧的上界了，好像听说$9d$就有反例，所以这个应该是上确界）

证明：
对于一个大于10d的数，它显然可以表示成$kd+r(k\ge 10,0\le m\le 9)$的形式，进而可以表示为$10d+r+(k-10)d(k\ge 10,0\le m\le 9)$的形式。
观察上式，$10d+r$显然是幸运数，$(k-10)d$也是幸运数，即可以表示成两个幸运数的和。
接着其实可以证明这是确界，如果取$9d$，$d=8,a_i=73$就是一个反例。所以10d是最小的。

判断：
对于大于$10d$的数，我们有上述结论。对于小于$10d$的数，可以暴力判断：每次减$d$，判断是否有那个数位上为$d$，直到小于$d$。

C Nezzar and Symmetric Array

回头再写

D Nezzar and Board

给定$n(2\le n\le 2\cdot 10^5)$个数$x_1,x_2,...,x_n(-10^{18}\le x_i\le 10^{18})$，以及一个数$k(-10^{18}\le k\le 10^{18})$。每次可以从$x_1,x_2,...,x_n$中选择两个数$x,y$(可以相同)，计算出$2x-y$再放回去(连同算出的$2x-y$一并放回去)，判断是否可以凑出$k$

先贴两个别的D题题解。[传送门1][传送门2]原本我D题就打算按照线性组合的思路做，但是没做出来。

这里按照官方题解的思路走：这是一道裴蜀定理的题。
首先给出裴蜀定理：对于关于$x,y$的不定方程$ax+by=c$当且仅当$gcd(a,b)|c$时有解。
并可以推广到任意个整数：$a_1{x}_1+a_2{x}_2+...+a_n{x}_n=c$当且仅当$gcd(a_1,a_2,...,a_n)|c$时有解。

思路:
$k=2x-y$也可以写成$k=x+(x-y)$，即表示成一个数加上它与另一个数的差。
事实上，一个可以多次通过$2x-y$表示出的数一定可以表示成另一个可表示出的数$k^{\prime }$与多组差的和：

$$k=k^{\prime }+\sum _{i,j}c(x_i-x_j)(c为常系数)$$

举个例子：设$k_1{k}_2$由$x_i,x_j,x_p,x_q$表示，即：
k 1 = x i + ( x i − x j ) , k 2 = x p + ( x p − x q )

$$\begin{aligned} k_1=x_i+(x_i-x_j),k_2=x_p+(x_p-x_q) \end{aligned}$$ k1​=xi​+(xi​−xj​),k2​=xp​+(xp​−xq​)​
那么$k_1{k}_2$表示的数为:
$$\begin{array}{rl}k& =2k_1-k_2\\ & =x_i+(x_i-x_j)+[2(x_i-x_p)+(x_q-x_j)]\\ & =k^{\prime }+\sum _{i,j}c(x_i-x_j)(c为常系数)\end{array}$$

上式还能继续化简:
k = k ′ + ∑ i , j c ( x i − x j ) k ′ = k ′ ′ + ∑ i , j c ( x i − x j ) . . . k ( m ) = x p + ∑ i , j c ( x i − x j )

$$\begin{aligned} k=k'+&\sum_{i,j}c(x_i-x_j)\\ k'=k''+&\sum_{i,j}c(x_i-x_j)\\ &...\\ k^{(m)}=x_p+&\sum_{i,j}c(x_i-x_j)\\ \end{aligned}$$ k=k′+k′=k′′+k(m)=xp​+​i,j∑​c(xi​−xj​)i,j∑​c(xi​−xj​)...i,j∑​c(xi​−xj​)​
得
$$\begin{array}{rl}k& =x_p+\sum _{i,j}c(x_i-x_j)\\ & =x_1+(x_p-x_1)+\sum _{i,j}c(x_i-x_j)\\ & =x_1+\sum _{i,j}c(x_i-x_j)\end{array}$$

而我们想要$k=x_1+{\sum }_{i,j}c(x_i-x_j)$，也即${\sum }_{i,j}c(x_i-x_j)=k-x_1$。
也就是$k-x_1$能否用两个数的差值表示。也就转化到了裴蜀定理，如果所有差值的最大公约数能够整除$k-x_1$，那么就能够凑出$k$

判断：
虽然能够做到这很不容易，但到这步得到的结论依然不尽如人意。如果真就按照上面思路，那我们需要求出任意两个数的差值。在$n(2\le n\le 2\cdot 10^5)$的要求下显然可能是正解。

那么应该怎么优化呢?

考虑下式:$gcd(a,b,a+b)=gcd(a,b)$。
证明十分显然,如果$gcd(a,b)=g$,那么有$g|a,g|b$,显然也有$g|(a+b)$。所以$gcd(a,b,a+b)=gcd(a,b)$

那么,如果我们求出了$x_2-x_1,x_3-x_2$的$gcd$,也就相当于求得了$x_2-x_1,x_3-x_2,x_3-x_1$的$gcd$。推广一下,只要我们求出$x_2-x_1,x_3-x_2,x_n-x_{n-1}$的$gcd$,也就相当于求出来任意两数之差的$gcd$

于是就可以判断:$gcd(x_2-x_1,x_3-x_2,...,x_n-x_{n-1})$是否整除$k-x_1$即可:

最后给出AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
typedef long long ll;
ll x[maxn];

ll gcd(ll a, ll b)
{
	while (b) {
		ll tmp = a % b;
		a = b;
		b = tmp;
	}
	return a;
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--) {
		int n; ll k;
		scanf("%lld%lld", &n, &k);
		for (int i = 0; i < n; i++) {
			scanf("%lld", &x[i]);
		}
		sort(x, x + n);
		ll g = 0;
		for (int i = 1; i < n; i++) {
			g = gcd(g, x[i] - x[i - 1]);
		}
		if ((k - x[0]) % g) {
			printf("NO\n");
		}
		else {
			printf("YES\n");
		}
	}

	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

E Nezzar and Binary String

F Nezzar and Nice Beatmap