D.Nezzar and Board
生肉{:target=”_blank”}
这题可能是该题解中证明过程最复杂的题了
题目翻译
黑板上写了 $x _ 1, x _ 2, \cdots, x _ n$ 这 $n$ 个数,$\text {Nezzar}$ 可以多次进行如下操作:
挑选黑板上的两个整数 $x, y$ (可以相同),将 $2x - y$ 写到黑板上。
注意不会将已选的数删掉。
$\text {Nezzar}$ 想知道,是否可以通过多次执行上述操作,得到 $k$。
输入
第一行包含一个正整数 $t \ (1 \leq t \leq 10 ^ 5)$,表示测试数据组数。
对于每组测试数据:
第一行包含一个整数 $n, k \ (1 \leq n \leq 2 \times 10 ^ 5, -10 ^ {18} \leq k \leq 10 ^ {18})$。
第二行包含 $n$ 个正整数 $x _ 1, x _ 2, \cdots, x _ n \ (- 10 ^ {18} \leq x _ i \leq 10 ^ {18})$。
数据保证所有 $n$ 的和不超过 $2 \times 10 ^ 5$。
输出
对于每组测试数据,如果能得到 $k$,则输出 YES
,否则输出 NO
。
样例输入
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
样例输出
YES
YES
NO
YES
YES
NO
算法
(猜结论,推式子,数论,裴蜀定理) $O(n \log n)$
性质:只有两个数 $x, y$ 时,我们可以得到 $k$,当且仅当 $\exists m \in \mathbb Z$,使得 $k = x + m (x - y)$。
(下文中出现的所有字母表示的都是整数)
充分性证明:
证明其充分性,即证明命题:通过上述操作,可以得到任意的 $x + m (x - y)$。
当 $m = 0$ 时,该式为 $x$,故当 $m = 0$ 时命题成立。
因为 $2x - y = x + (x - y)$,故当 $m = 1$ 时命题成立
$1.$ 证明当 $m \geq 0$ 时,命题成立:
设 $M \geq 2$,假设对于任意 $0 \leq m < M$ 的 $m$ 都成立,考虑当 $m = M$ 时:
$1. (1)$ 当 $M$ 是奇数时:
$$ M \geq 2 > 1 \ \Rightarrow \ 2N > M + 1 \ \Rightarrow \ \begin {aligned} M > \frac {M + 1} 2 \end {aligned} $$
根据假设,我们可以得到 $\begin {aligned} x + \frac {M + 1} 2 (x - y) \end {aligned}$
我们又已知可以得到 $2x - y$,我们可以对这两个数执行上述操作,得到:
$$ \begin {aligned} &\ 2 \times (x + \frac {M + 1} 2 (x - y)) - (2x - y) \\\ \\\ & = 2 x + (M + 1) (x - y) - 2x + y \\\ \\\ & = y + (x - y) + M (x - y) \\\ \\\ & = x + M (x - y) \\\ \end {aligned} $$
故当 $M$ 为奇数时,命题当 $m = M$ 时成立。
$1. (2)$ 当 $M$ 为偶数时:
$$ M \geq 2 > 0 \ \Rightarrow \ 2N > M \ \Rightarrow \ \begin {aligned} M > \frac M 2 \end {aligned} $$
根据假设,我们可以得到 $\begin {aligned} x + \frac M 2 (x - y) \end {aligned}$
我们又已知可以得到 $x$,我们可以对这两个数执行上述操作,得到:
$$ \begin {aligned} &\ 2 \times (x + \frac M 2 (x - y)) - x \\\ \\\ & = 2 x + M (x - y) - x \\\ \\\ & = x + M (x - y) \\\ \end {aligned} $$
故当 $M$ 为偶数时,命题当 $m = M$ 时成立。
故对于所有 $m \geq 0$,命题成立。
$2.$ 证明当 $m < 0$ 时,命题成立:
因为 $m < 0$,所以 $-m > 0$
我们已证当 $m \geq 0$ 时,命题成立,故可以得到 $x + (-m) (x - y)$
我们已知可以得到 $x$,我们可以对这两个数执行上述操作,得到:
$$ \begin {aligned} &\ 2 x - (x + (-m) (x - y)) \\\ \\\ & = 2x - x + m (x - y) \\\ \\\ & = x + m (x - y) \\\ \end {aligned} $$
故当 $m < 0$ 时,命题成立。
故对于任意整数 $m$,命题成立。
必要性证明:
证明其必要性,即证明命题:通过上述操作得到的所有数,都可以表示成 $x + m (x - y)$ 的形式。
设通过上述操作得到的所有数的集合为 $S$。
那么证明该命题,等价于证明命题:$\forall a, b \in S, 2 a - b \in S$
因为 $a, b \in S$,可设 $a = x + m _ 1 (x - y), b = x + m _ 2 (x - y)$。
$ \begin {aligned} \text {那么有 } 2 a - b &\ = 2 \times (x + m _ 1 (x - y)) - (x + m _ 2 (x - y)) \\\ \\\ &\ = 2 x + 2 m _ 1 (x - y) - x - m _ 2 (x - y) \\\ \\\ &\ = x + (2 m _ 1 - m _ 2) (x - y) \\\ \end {aligned} $
所以 $2 a - b \in S$
故命题成立。
那么根据这个性质,我们可以解决输入中 $n = 2$ 的情况。
考虑拓展到 $n > 2$ 时:
结论:如果 $\exists m \in \mathbb Z$,使得 $k = x _ 1 + m \gcd(x _ 2 - x _ 1, x _ 3 - x _ 1, \cdots, x _ n - x _ 1)$,那么我们可以得到 $k$。
证明:
该命题当 $n = 2$ 时成立(即上述性质)
设 $N \geq 3$,假设该命题当 $n = N - 1$ 成立,考虑当 $n = N$ 时:
因为当 $n = N - 1$ 时成立,所以我们可以表示出所有 $x _ 1 + m \gcd(x _ 2 - x _ 1, x _ 3 - x _ 1, \cdots, x _ {N - 1} - x _ 1)$。
设 $d = \gcd(x _ 2 - x _ 1, x _ 3 - x _ 1, \cdots, x _ {N - 1} - x _ 1)$,那么我们可以表示出所有 $x _ 1 + m _ 1 d$。
考虑在集合 $\{x _ 1, x _ 2, \cdots, x _ {N - 1}\}$ 中,加入 $x _ N$。
根据上述性质,我们可以用 $x _ 1$ 和 $x _ N$ 组合出任何 $x _ 1 + m _ 2 (x _ 1 - x _ N)$。
令 $t = x _ 1 - x _ N$,则我们可以通过 $x _ 1$ 和 $x _ N$ 得到任意的 $x _ 1 + m _ 2 t$。
再次根据上述性质,通过 $x _ 1 + m _ 2 t$ 和 $x _ 1 + m _ 1 d$ ,可得到任意的 $x _ 1 + m _ 1 d + m _ 0 (x _ 1 + m _ 1 d - x _ 1 - m _ 2 t)$。
化简得 $x _ 1 + m _ 1 d + m _ 0 (m _ 1 d - m _ 2 t)$
根据裴蜀定理{:target=”_blank”},可得:存在 $r _ 1, r _ 2$,使得当 $m _ 1 = r _ 1, m _ 2 = r _ 2$ 时,$m _ 1 d - m _ 2 t = \gcd(d, t)$。
将 $m _ 1 = r _ 1, m _ 2 = r _ 2$ 代入得
$$ \begin {aligned} &\ x _ 1 + r _ 1 d + m _ 0 \gcd(d, t) \\\ \\\ = &\ x _ 1 + (\frac {r _ 1 d} {\gcd(d, t)} + m _ 0) \gcd(d, t) \\\ \end {aligned} $$
令 $\begin {aligned} m = \frac {r _ 1 d} {\gcd(d, t)} + m _ 0 \end {aligned}$,则我们可以得到任意的 $x _ 1 + m \gcd(d, t)$。
即 $x _ 1 + m \gcd(x _ 2 - x _ 1, x _ 3 - x _ 1, \cdots, x _ N - x _ 1)$。
故当 $n = N$ 时,该命题成立。
故对于任意正整数 $n$,该命题成立。
有了该结论之后,我们可以求出 $d = \gcd(x _ 2 - x _ 1, x _ 3 - x _ 1, \cdots, x _ n - x _ 1)$,然后判断 $x _ 1$ 和 $k$ 在 $\text { mod } d$ 意义下是否同余即可。
时间复杂度
我们会求 $n$ 次最大公约数,每次复杂度为 $O(\log n)$,故总时间复杂度为 $O(n \log n)$。
C++ 代码
#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = 200005;
int n;
ll x[N], d, k;
ll gcd(ll a, ll b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int task;
scanf("%d", &task);
while (task -- )
{
scanf("%d%lld", &n, &k);
d = 0;
for (int i = 1; i <= n; i ++ )
{
scanf("%lld", x + i);
d = gcd(x[i] - x[1], d);
}
if ((x[1] - k) % d) puts("NO");
else puts("YES");
}
return 0;
}
$\text{Q:}$ 为什么这么晚才发 $\text{D}$ 题题解?
$\text{A:}$ 对你没猜错这个证明我证了三天。
$$ $$
看不懂呜呜呜
这证明确实不好懂,建议先记结论(虽然这个结论好像没啥大用。。
tql,比网上的博客详细多了
%
求 E 的题解qaq
已更{:target=”_blank”}
Orz