P16462 [UOI 2026] Divisors

You are given $2n$ integers $b_1, b_2, \dots, b_{2n}$ and an integer $x$. For all $i$, it holds that $1 \le b_i \le x$. In one operation, you may choose any index $i$ ($1 \le i \le 2n$) and increase the number $b_i$ by $1$. You need to perform no more than $\left\lfloor \frac{x}{2} \right\rfloor$ operations and split all numbers into $n$ pairs so that in each pair, after performing the operations, one number is divisible by the other. In other words, you need to find non-negative integers $d_1, d_2, \dots, d_{2n}$ and a partition of the indices $1, 2, \dots, 2n$ into $n$ pairs such that: - $\sum\limits_{i=1}^{2n} d_i \le \left\lfloor \frac{x}{2} \right\rfloor$, that is, the sum of all $d_i$ does not exceed $\frac{x}{2}$ rounded down; - if $c_i = b_i + d_i$, then for every pair of indices $(u, v)$, either $c_u \mid c_v$ or $c_v \mid c_u$, that is, either $c_u$ divides $c_v$ or $c_v$ divides $c_u$. It is guaranteed that for the given constraints, an answer always exists. $\left\lfloor y \right\rfloor$ denotes the greatest integer not exceeding $y$. For example, $\left\lfloor 7/2 \right\rfloor = 3$.

The first line contains one integer $t$ $(1 \le t \le 10^4)$ --- the number of test cases. Each test case consists of two lines. The first line of a test case contains two integers $n$ and $x$ ($1 \le n \le 10^5$, $1 \le x \le 10^9$). The second line contains $2n$ integers $b_1, b_2, \dots, b_{2n}$ ($1 \le b_i \le x$). It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

For each test case, output the answer in the following format. First, output $n$ lines. In the $j$-th of them, output two integers $u_j$ and $v_j$ --- the indices of the numbers that form the $j$-th pair. Each index from $1$ to $2n$ must appear in exactly one pair. After that, output one line with $2n$ integers $d_1, d_2, \dots, d_{2n}$, where $d_i$ is the number of operations performed on the number $b_i$. The following must hold: $ d_i \ge 0 $ for all $1 \le i \le 2n$, and also $ \sum\limits_{i=1}^{2n} d_i \le \left\lfloor \frac{x}{2} \right\rfloor. $ Let $c_i = b_i + d_i$. For each printed pair $(u_j, v_j)$, it must hold that: $ c_{u_j} \mid c_{v_j} \quad \text{or} \quad c_{v_j} \mid c_{u_j}. $ If there are multiple correct answers, you may output any of them.

In the first example, we can split the numbers into pairs $(3, 3)$, $(1, 8)$, $(4, 2)$, and $(5, 5)$. In each pair, one number is divisible by the other, so we do not perform any operations. In the second example, we add $3$ to the first number and $1$ to the last one. We obtain the new array: $[10, 2, 6, 3, 5, 9]$. After that, we split the numbers into pairs $(2, 6)$, $(3, 9)$, and $(10, 5)$. The total number of operations is $3+1 = 4 \leq \left\lfloor \frac{x}{2} \right\rfloor = 4$. Note that this is not the minimum possible number of operations. ### Scoring - ($6$ points): $t = 1$, $n \le 4$, $b_i \le 50$. - ($7$ points): $t = 1$, $n \le 10$, $b_i \le 10^4$. - ($7$ points): $t = 1$, $n \le 10$. - ($10$ points): $b_i \ge \left\lceil \frac{x}{2} \right\rceil$ for all $i$. - ($10$ points): for each $i$, either $b_i \le \left\lfloor \frac{x}{6} \right\rfloor$ or $b_i \ge x - \left\lfloor \frac{x}{6} \right\rfloor$. - ($10$ points): the answer can be obtained without performing any operations. All numbers are powers of prime numbers, all numbers do not exceed $10^6$, $t \le 10$. - ($13$ points): the answer can be obtained without performing any operations. Each number is a product of at most two prime numbers, each prime number appears in the factorization of all numbers in total at most twice, all numbers do not exceed $10^6$, $t \le 10$. - ($17$ points): There exists an answer where the adjacent numbers of the initial array can be paired: $(1, 2), (3, 4), \ldots, (2n - 1, 2n)$. Also, $\sum n \le 1000$ and $b_i \le 10^9$. - ($20$ points): no additional constraints.