本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-12 10:01:54

:::::info[题目基本信息] 考察：构造（$3000$）。
题目简介：
给定非正整数序列 $\{a_n\}$，有操作：

• 选择 $x,y\in[1,n]$，使得 $a_x\le a_y$，同时令 $a_y\leftarrow a_y-a_x,a_x\leftarrow 2a_x$。

要求一系列操作完成后序列中恰好有两个数非 $0$，要求构造一组操作，操作数不得超过 $10^6$，无解给出 -1。
数据范围：

• $1\le n\le 1000$
• $0\le \sum a_i\le 10^6$ ::::: 显然，操作不会使序列中 $0$ 的个数减少，同时也不会使 $0$ 的个数一次性减少的个数超过 $1$，所以在序列非 $0$ 个数小于 $2$ 时便无解。
  我们先考虑让两个数来回操作的情况，但是这样很快就寄了，比如我们无法通过操作把 $1,2$ 两个数中的一个变为 $0$。
  那我们再考虑 $3$ 个数内部操作，我们先考虑特殊情况。
  钦定操作的三个数为 $a_x.a_y,a_z$，且 $a_x\le a_y\le a_z$。
  容易发现，在 $a_x\mid a_y$ 时，我们可以通过对于 $k=\dfrac{a_y}{a_x}$ 二进制下的从低到高的每一位进行分讨（设目前处理到了第 $i$ 位）：
• 当第 $i$ 位为 $1$ 时，操作 $(x,y)$。
• 当第 $i$ 位为 $0$ 时，操作 $(x,z)$。

这时我们就能把 $a_y$ 清空成 $0$，且由于 $a_z$ 的减少量小于 $a_y$ 的减少量，故 $a_z$ 不会被清零，这样我们就将一个数清为 $0$ 了。
但是在 $a_x\nmid a_y$ 时又该如何呢？
令 $p=a_y\bmod a_x$，最终 $a_y\leftarrow p$，这时将 $a_x,a_y,a_z$ 重新排序 $a_y$ 一定会被被排序到 $a_x$ 的位置上，成为 $a'_x$，这时 $a'_x=p<a_x$，那么这样下去早晚会产生 $0$。
这样我们就有了一种构造方案，现在我们来观察一下复杂度。
容易发现，令 $a_x\leftarrow a_y\bmod a_x$ 的一轮操作构造复杂度为 $\Theta(\log V)$ 次。同时由于有结论（下文钦定 $a\ge b$）：
$$a\bmod b<\frac{a}{2}$$ :::::success[证明] 当 $b>\dfrac{a}{2}$ 时，$a\bmod b=a-b<a-\dfrac{a}{2}=\dfrac{a}{2}$。
当 $b\le\dfrac{a}{2}$ 时，$a\bmod b<b\le\dfrac{a}{2}$。
::::: 这样轮数大概是在 $\Theta(\log V)$ 量级的，但是这个东西和辗转相除法等价在哪？？？？故本人目前不会严谨的证明。
这样构造复杂度大约是在 $\Theta(n\log^2 V)$ 的，反正能过。
时间复杂度为 $\Theta(n\log^2 V)$，空间复杂度为 $\Theta(n)$。

code