P16462 [UOI 2026] Divisors

给定 $2n$ 个整数 $b_1, b_2, \dots, b_{2n}$ 和一个整数 $x$。对于所有 $i$，满足 $1 \le b_i \le x$。 在一次操作中，你可以选择任意下标 $i$ ($1 \le i \le 2n$)，并将该数 $b_i$ 增加 $1$。 你需要执行不超过 $\left\lfloor \frac{x}{2} \right\rfloor$ 次操作，并将所有数分成 $n$ 对，使得在操作完成后，每对中一个数能被另一个数整除。 换句话说，你需要找到非负整数 $d_1, d_2, \dots, d_{2n}$ 以及下标 $1, 2, \dots, 2n$ 的一个 $n$ 对划分，使得： - $\sum\limits_{i=1}^{2n} d_i \le \left\lfloor \frac{x}{2} \right\rfloor$，即所有 $d_i$ 之和不超过 $\frac{x}{2}$ 向下取整的值； - 若记 $c_i = b_i + d_i$，则对于每一对下标 $(u, v)$，要么 $c_u \mid c_v$，要么 $c_v \mid c_u$，即 $c_u$ 整除 $c_v$ 或 $c_v$ 整除 $c_u$。 保证在给定的约束下，答案总是存在。 $\left\lfloor y \right\rfloor$ 表示不超过 $y$ 的最大整数。例如，$\left\lfloor 7/2 \right\rfloor = 3$。

第一行包含一个整数 $t$ $(1 \le t \le 10^4)$ —— 测试数据的组数。 每组测试数据包含两行。 测试数据的第一行包含两个整数 $n$ 和 $x$ ($1 \le n \le 10^5$, $1 \le x \le 10^9$)。 第二行包含 $2n$ 个整数 $b_1, b_2, \dots, b_{2n}$ ($1 \le b_i \le x$)。 保证所有测试数据的 $n$ 之和不超过 $10^5$。

对于每组测试数据，按以下格式输出答案。 首先，输出 $n$ 行。在第 $j$ 行中，输出两个整数 $u_j$ 和 $v_j$ —— 组成第 $j$ 对的两个数的原始下标。 每个从 $1$ 到 $2n$ 的下标必须在所有对中恰好出现一次。 然后，输出一行包含 $2n$ 个整数 $d_1, d_2, \dots, d_{2n}$，其中 $d_i$ 是对数字 $b_i$ 执行的操作次数。必须满足：对于所有 $1 \le i \le 2n$，有 $d_i \ge 0$，并且 $\sum\limits_{i=1}^{2n} d_i \le \left\lfloor \frac{x}{2} \right\rfloor$。 令 $c_i = b_i + d_i$。对于输出的每一对 $(u_j, v_j)$，必须满足：$c_{u_j} \mid c_{v_j}$ 或 $c_{v_j} \mid c_{u_j}$。 如果存在多个正确答案，你可以输出其中任意一个。

在第一个例子中，我们可以将数字分成对 $(3, 3)$、$(1, 8)$、$(4, 2)$ 和 $(5, 5)$。每一对中，一个数都能被另一个整除，因此我们不需要执行任何操作。 在第二个例子中，我们将第一个数增加 $3$，最后一个数增加 $1$。我们得到新的数组：$[10, 2, 6, 3, 5, 9]$。随后，我们将数字分成对 $(2, 6)$、$(3, 9)$ 和 $(10, 5)$。操作总次数为 $3 + 1 = 4 \le \left\lfloor \frac{x}{2} \right\rfloor = 4$。注意，这并非可能的最少操作次数。 ### 计分 - ($6$ 分)：$t = 1$，$n \le 4$，$b_i \le 50$。 - ($7$ 分)：$t = 1$，$n \le 10$，$b_i \le 10^4$。 - ($7$ 分)：$t = 1$，$n \le 10$。 - ($10$ 分)：对于所有 $i$，有 $b_i \ge \left\lceil \frac{x}{2} \right\rceil$。 - ($10$ 分)：对于每个 $i$，要么 $b_i \le \left\lfloor \frac{x}{6} \right\rfloor$，要么 $b_i \ge x - \left\lfloor \frac{x}{6} \right\rfloor$。 - ($10$ 分)：可以不执行任何操作就得到答案。所有数都是素数的幂，所有数不超过 $10^6$，$t \le 10$。 - ($13$ 分)：可以不执行任何操作就得到答案。每个数都是至多两个素数的乘积，每个素数在所有数的分解中总共出现至多两次，所有数不超过 $10^6$，$t \le 10$。 - ($17$ 分)：存在一个答案，使得初始数组的相邻数可以两两配对：$(1, 2), (3, 4), \ldots, (2n - 1, 2n)$。同时 $\sum n \le 1000$ 且 $b_i \le 10^9$。 - ($20$ 分)：无额外限制。 翻译由 DeepSeek V4 Pro 完成