比赛链接

给定 $n$ 个不同的 $x_i$，每次可以选取一对 $x,y$，得到 $2x-y$。(注意该操作不会删去原有的 $x,y$)

问是否能经过有限次操作得到 $k$。

不妨设 $b=\min(x_i)$，记 $a_i=x_i-b,k'=k-b$，于是有 $2x_i-x_j=2a_i-2b-a_j+b=(2a_i-a_j)-b$。

如果用 $a_i$ 替代 $x_i$，$k'$ 替代 $k$，则所有结果相当于都平移了 $b$，对答案不影响。于是不妨设序列为 $0,a_2,a_3\cdots a_n$。

首先对于 $0,a$，有 $2a-0=2a,2*(2a)-a=3a,2*(3a)-(2a)=4a$，于是可以得到所有 $a$ 的倍数。

然后假设 $n=t$ 时 $g_t$ 一定可以得到，于是能得到 $k$ 当且仅当 $g_t=\text{gcd}(a_2,a_3\cdots a_t)\mid k$ 。

$n=2$ 时相当于 $0,a$ 的情况，显然成立。

$n=t+1$ 时，根据裴蜀定理，知存在 $x,y$ 满足

$$ x*g_t-y*a_{t+1}=\text{gcd}(g_t,a_{t+1})=g_{t+1} $$

根据归纳假设，可以得到 $g_t$。如果 $x=2x'$，则先得到 $x'*g_t$ 和 $y*a_{t+1}$，于是 $g_{t+1}=2x'g_t-y*a_{t+1}$。

同理 $y$ 为偶数时也能得到 $g_{t+1}$。下证一定存在 $x,y$ 满足至少有一个偶数。

假设得到的一组 $x,y$ 为全为奇数，则记 $c=\frac {g_t}{g_{t+1}},d=\frac {a_{t+1}}{g_{t+1}}$，于是有

$$ 1=x*c-y*d=(x+d)*c-(y+c)*d $$

因为 $(c,d)=1$，所以 $c,d$ 中至少一个奇数，于是 $x+d,y+c$ 中至少一个偶数，证毕。