Make Array Good

题意翻译

## 题目描述 我们称一个长度为 $m$ 序列 $b$ 是好的，当且仅当对于每一个二元组 $i,j \in [1,m]$，都有 $\min(b_i,b_j) | \max(b_i,b_j)$。 其中 $|$ 表示整除，即 $a|b$ 表示 $a$ 被 $b$ 整除。 接下来给定一个长度为 $n$ 的序列 $a$。 你可以对他进行以下操作： - 选择 $i(1 \le i \le n)$ 和一个非负整数 $x(0 \le x \le a_i)$，将 $a_i$ 变成 $a_i+x$。 - 你应该保证在操作后 $a_i \le 10^{18}$。 你需要使用最多 $n$ 个操作，使得 $a$ 序列成为一个好的序列，可以证明一定是可以构造出来的。 请输出构造方案。 ## 输入格式 第一行一个正整数 $t(1 \le t \le 10^4)$，表示数据组数。 对于每组数据： 第一行一个正整数 $n(1 \le n \le 10^5)$ 表示序列的长度。 接下来 $n$ 个正整数 $a_1,a_2,\dots,a_n(1 \le a_i \le 10^9)$。 ## 输出格式 对于每组数据： 第一行一个整数 $p(0 \le p \le n)$，表示解决方案的操作数。 接下来 $p$ 行，每行两个用空格分开的整数 $i$ 和 $x$。 不需要最小化方案数。

题目描述

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) $ . You are given an array $ a $ of $ n $ positive integers. You can perform the following operation: - 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 $ . - After this operation, $ a_i \leq 10^{18} $ should be satisfied. 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.

输入输出格式

输入格式

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. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 10^5 $ ) — the length of the array $ a $ . 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 $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test, output a single integer $ p $ ( $ 0 \leq p \leq n $ ) — denoting the number of operations in your solution. In each of the following $ p $ lines, output two space-separated integers — $ i $ and $ x $ . You do not need to minimize the number of operations. It can be proven that a solution always exists.

输入输出样例

输入样例 #1

4
4
2 3 5 5
2
4 8
5
3 4 343 5 6
3
31 5 17

输出样例 #1

4
1 2
1 1
2 2
3 0
0
5
1 3
1 4
2 1
5 4
3 7
3
1 29
2 5
3 3

说明

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. In the second test case, array $ a $ is already good. In the third test case, after performing the operations, array $ a $ becomes $ [10,5,350,5,10] $ , which is good. In the fourth test case, after performing the operations, array $ a $ becomes $ [60,10,20] $ , which is good.

**题目大意：**

定义一个长度为 $ m $ 的序列 $ b $ 为“好的”，当且仅当对于任意两个不同的位置 $ i,j $（$ 1 \leq i,j \leq m $），都有最大值 $ \max(b_i, b_j) $ 能被最小值 $ \min(b_i, b_j) $ 整除。

给定一个长度为 $ n $ 的序列 $ a $，你可以进行以下操作：

- 选择一个下标 $ i $（$ 1 \leq i \leq n $）和一个非负整数 $ x $（$ 0 \leq x \leq a_i $），然后将 $ a_i $ 变为 $ a_i + x $。
- 操作后，$ a_i $ 的值需要满足 $ a_i \leq 10^{18} $。

你的目标是通过最多 $ n $ 次操作，使得序列 $ a $ 变为一个“好的”序列。题目保证在给定条件下，一定存在至少一种操作方案。

**输入输出数据格式：**

**输入格式：**

第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $），表示测试用例的数量。

每个测试用例包含两行：

- 第一行包含一个整数 $ n $（$ 1 \leq n \leq 10^5 $），表示序列 $ a $ 的长度。
- 第二行包含 $ n $ 个用空格分隔的整数 $ a_1, a_2, \ldots, a_n $（$ 1 \leq a_i \leq 10^9 $），代表序列 $ a $ 的每个元素的值。

保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。

**输出格式：**

对于每个测试用例，输出一行一个整数 $ p $（$ 0 \leq p \leq n $），表示你的操作方案中操作的次数。

接下来输出 $ p $ 行，每行两个用空格分隔的整数 $ i $ 和 $ x $，代表每次操作选择的下标和增加的值。

不需要最小化操作次数，题目保证至少存在一种解决方案。**题目大意：** 定义一个长度为 $ m $ 的序列 $ b $ 为“好的”，当且仅当对于任意两个不同的位置 $ i,j $（$ 1 \leq i,j \leq m $），都有最大值 $ \max(b_i, b_j) $ 能被最小值 $ \min(b_i, b_j) $ 整除。 给定一个长度为 $ n $ 的序列 $ a $，你可以进行以下操作： - 选择一个下标 $ i $（$ 1 \leq i \leq n $）和一个非负整数 $ x $（$ 0 \leq x \leq a_i $），然后将 $ a_i $ 变为 $ a_i + x $。 - 操作后，$ a_i $ 的值需要满足 $ a_i \leq 10^{18} $。 你的目标是通过最多 $ n $ 次操作，使得序列 $ a $ 变为一个“好的”序列。题目保证在给定条件下，一定存在至少一种操作方案。 **输入输出数据格式：** **输入格式：** 第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $），表示测试用例的数量。 每个测试用例包含两行： - 第一行包含一个整数 $ n $（$ 1 \leq n \leq 10^5 $），表示序列 $ a $ 的长度。 - 第二行包含 $ n $ 个用空格分隔的整数 $ a_1, a_2, \ldots, a_n $（$ 1 \leq a_i \leq 10^9 $），代表序列 $ a $ 的每个元素的值。 保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。 **输出格式：** 对于每个测试用例，输出一行一个整数 $ p $（$ 0 \leq p \leq n $），表示你的操作方案中操作的次数。 接下来输出 $ p $ 行，每行两个用空格分隔的整数 $ i $ 和 $ x $，代表每次操作选择的下标和增加的值。 不需要最小化操作次数，题目保证至少存在一种解决方案。