1762B.md (2237B)
1 Source: https://codeforces.com/problemset/problem/1762/B 2 3 B. Make Array Good 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 An array $b$ of $m$ positive integers is good if for all pairs $i$ and $j$ ($1 \leq i,j \leq m$), $\max(b_i,b_j)$ is divisible by $\min(b_i,b_j)$. 22 23 You are given an array $a$ of $n$ positive integers. You can perform the following operation: 24 25 * Select an index $i$ ($1 \leq i \leq n$) and an integer $x$ ($0 \leq x \leq a_i$) and add $x$ to $a_i$, in other words, $a_i := a_i+x$. 26 * After this operation, $a_i \leq 10^{18}$ should be satisfied. 27 28 You have to construct a sequence of at most $n$ operations that will make $a$ good. It can be proven that under the constraints of the problem, such a sequence of operations always exists. 29 30 Input 31 32 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows. 33 34 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$) — the length of the array $a$. 35 36 The second line of each test case contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \leq 10^9$) — representing the array $a$. 37 38 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 39 40 Output 41 42 For each test, output a single integer $p$ ($0 \leq p \leq n$) — denoting the number of operations in your solution. 43 44 In each of the following $p$ lines, output two space-separated integers — $i$ and $x$. 45 46 You do not need to minimize the number of operations. It can be proven that a solution always exists. 47 48 Example 49 50 Input 51 52 ``` 53 4 54 55 4 56 57 2 3 5 5 58 59 2 60 61 4 8 62 63 5 64 65 3 4 343 5 6 66 67 3 68 69 31 5 17 70 ``` 71 72 Output 73 74 ``` 75 4 76 1 2 77 1 1 78 2 2 79 3 0 80 0 81 5 82 1 3 83 1 4 84 2 1 85 5 4 86 3 7 87 3 88 1 29 89 2 5 90 3 3 91 ``` 92 93 Note 94 95 In the first test case, array $a$ becomes $[5,5,5,5]$ after the operations. It is easy to see that $[5,5,5,5]$ is good. 96 97 In the second test case, array $a$ is already good. 98 99 In the third test case, after performing the operations, array $a$ becomes $[10,5,350,5,10]$, which is good. 100 101 In the fourth test case, after performing the operations, array $a$ becomes $[60,10,20]$, which is good.