Equalize by Divide

题目描述

You are given an array $ a_1, a_2, \ldots, a_n $ of positive integers. You can make this operation multiple (possibly zero) times: - Choose two indices $ i $ , $ j $ ( $ 1 \leq i, j \leq n $ , $ i \neq j $ ). - Assign $ a_i := \lceil \frac{a_i}{a_j} \rceil $ . Here $ \lceil x \rceil $ denotes $ x $ rounded up to the smallest integer $ \geq x $ . Is it possible to make all array elements equal by some sequence of operations (possibly empty)? If yes, print any way to do it in at most $ 30n $ operations. It can be proven, that under the problem constraints, if some way exists to make all elements equal, there exists a way with at most $ 30n $ operations.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. Descriptions of test cases follow. The first line of each test case description contains a single integer $ n $ ( $ 1 \leq n \leq 100 $ ). The second line of each test case description contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ). It is guaranteed, that the sum of $ n $ for all test cases does not exceed $ 1000 $ .

输出格式

For each test case print a single integer $ q $ ( $ -1 \leq q \leq 30n $ ). If $ q=-1 $ , there is no solution, otherwise $ q $ is equal to the number of operations. If $ q \geq 0 $ , on the next $ q $ lines print two integers $ i $ , $ j $ ( $ 1 \leq i, j \leq n $ , $ i \neq j $ ) — descriptions of operations. If there are multiple solutions, you can print any.

输入输出样例

输入样例 #1

10
1
100
3
1 1 1
2
2 1
2
5 5
3
4 3 2
4
3 3 4 4
2
2 100
5
5 3 6 7 8
6
3 3 80 3 8 3
4
19 40 19 55

输出样例 #1

0
0
-1
0
2
1 3
2 1
4
3 1
4 2
1 3
2 4
6
2 1
2 1
2 1
2 1
2 1
2 1
8
5 2
4 2
3 2
1 3
1 3
2 1
4 1
5 1
4
5 1
3 1
3 1
3 1
9
4 2
2 1
1 2
1 2
3 2
3 2
1 4
2 4
3 4

说明

In the first and second, fourth test cases all numbers are equal, so it is possible to do nothing. In the third test case, it is impossible to make all numbers equal. In the fifth test case: $ [\color{red}{4}, 3, \color{blue}{2}] \to [\color{blue}{2}, \color{red}{3}, 2] \to [2, 2, 2] $ . In the sixth test case: $ [\color{blue}{3}, 3, \color{red}{4}, 4] \to [3, \color{blue}{3}, 2, \color{red}{4}] \to [\color{red}{3}, 3, \color{blue}{2}, 2] \to [2, \color{red}{3}, 2, \color{blue}{2}] \to [2, 2, 2, 2] $ . Here the red numbers are $ i $ indices (that will be assigned), blue numbers are $ j $ indices.

**题目：通过除法使数组元素相等**

**题目描述：**
给定一个正整数数组 $ a_1, a_2, \ldots, a_n $。

你可以进行多次（可能为零次）以下操作：

- 选择两个索引 $ i $, $ j $（$ 1 \leq i, j \leq n $，$ i \neq j $）。
- 将 $ a_i $ 赋值为 $ \lceil \frac{a_i}{a_j} \rceil $。这里 $ \lceil x \rceil $ 表示 $ x $ 向上取整到最小的整数 $ \geq x $。

通过一系列操作（可能为空操作），是否可以使数组所有元素相等？如果可以，请在最多 $ 30n $ 次操作内输出一种方法。

可以证明，在问题的约束下，如果存在某种方法使所有元素相等，那么一定存在一种最多 $ 30n $ 次操作的方法。

**输入输出格式：**

**输入格式：**
第一行包含一个整数 $ t $（$ 1 \leq t \leq 1000 $）——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $ n $（$ 1 \leq n \leq 100 $）。

每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \leq a_i \leq 10^9 $）。

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

**输出格式：**
对于每个测试用例，打印一个整数 $ q $（$ -1 \leq q \leq 30n $）。如果 $ q=-1 $，则没有解决方案；否则 $ q $ 等于操作的数量。

如果 $ q \geq 0 $，在接下来的 $ q $ 行中，每行打印两个整数 $ i $, $ j $（$ 1 \leq i, j \leq n $，$ i \neq j $）——操作的描述。

如果有多个解决方案，你可以输出任何一个。

**输入输出样例：**

**输入样例 #1：**
```
10
1
100
3
1 1 1
2
2 1
2
5 5
3
4 3 2
4
3 3 4 4
2
2 100
5
5 3 6 7 8
6
3 3 80 3 8 3
4
19 40 19 55
```

**输出样例 #1：**
```
0
0
-1
0
2
1 3
2 1
4
3 1
4 2
1 3
2 4
6
2 1
2 1
2 1
2 1
2 1
2 1
8
5 2
4 2
3 2
1 3
1 3
2 1
4 1
5 1
4
5 1
3 1
3 1
3 1
9
4 2
2 1
1 2
1 2
3 2
3 2
1 4
2 4
3 4
```

**说明：**
在第一个和第二个、第四个测试用例中，所有数字都相等，因此可以不做任何操作。

在第三个测试用例中，不可能使所有数字相等。

在第五个测试用例中：$ [\color{red}{4}, 3, \color{blue}{2}] \to [\color{blue}{2}, \color{red}{3}, 2] \to [2, 2, 2] $。

在第六个测试用例中：$ [\color{blue}{3}, 3, \color{red}{4}, 4] \to [3, \color{blue}{3}, 2, \color{red}{4}] \to [\color{red}{3}, 3, \color{blue}{2}, 2] \to [2, \color{red}{3}, 2, \color{blue}{2}] \to [2, 2, 2, 2]$。

这里红色数字是 $ i $ 索引（将被赋值），蓝色数字是 $ j $ 索引。**题目：通过除法使数组元素相等** **题目描述：** 给定一个正整数数组 $ a_1, a_2, \ldots, a_n $。 你可以进行多次（可能为零次）以下操作： - 选择两个索引 $ i $, $ j $（$ 1 \leq i, j \leq n $，$ i \neq j $）。 - 将 $ a_i $ 赋值为 $ \lceil \frac{a_i}{a_j} \rceil $。这里 $ \lceil x \rceil $ 表示 $ x $ 向上取整到最小的整数 $ \geq x $。 通过一系列操作（可能为空操作），是否可以使数组所有元素相等？如果可以，请在最多 $ 30n $ 次操作内输出一种方法。 可以证明，在问题的约束下，如果存在某种方法使所有元素相等，那么一定存在一种最多 $ 30n $ 次操作的方法。 **输入输出格式：** **输入格式：** 第一行包含一个整数 $ t $（$ 1 \leq t \leq 1000 $）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $（$ 1 \leq n \leq 100 $）。 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \leq a_i \leq 10^9 $）。 保证所有测试用例的 $ n $ 之和不超过 $ 1000 $。 **输出格式：** 对于每个测试用例，打印一个整数 $ q $（$ -1 \leq q \leq 30n $）。如果 $ q=-1 $，则没有解决方案；否则 $ q $ 等于操作的数量。 如果 $ q \geq 0 $，在接下来的 $ q $ 行中，每行打印两个整数 $ i $, $ j $（$ 1 \leq i, j \leq n $，$ i \neq j $）——操作的描述。 如果有多个解决方案，你可以输出任何一个。 **输入输出样例：** **输入样例 #1：** ``` 10 1 100 3 1 1 1 2 2 1 2 5 5 3 4 3 2 4 3 3 4 4 2 2 100 5 5 3 6 7 8 6 3 3 80 3 8 3 4 19 40 19 55 ``` **输出样例 #1：** ``` 0 0 -1 0 2 1 3 2 1 4 3 1 4 2 1 3 2 4 6 2 1 2 1 2 1 2 1 2 1 2 1 8 5 2 4 2 3 2 1 3 1 3 2 1 4 1 5 1 4 5 1 3 1 3 1 3 1 9 4 2 2 1 1 2 1 2 3 2 3 2 1 4 2 4 3 4 ``` **说明：** 在第一个和第二个、第四个测试用例中，所有数字都相等，因此可以不做任何操作。 在第三个测试用例中，不可能使所有数字相等。 在第五个测试用例中：$ [\color{red}{4}, 3, \color{blue}{2}] \to [\color{blue}{2}, \color{red}{3}, 2] \to [2, 2, 2] $。 在第六个测试用例中：$ [\color{blue}{3}, 3, \color{red}{4}, 4] \to [3, \color{blue}{3}, 2, \color{red}{4}] \to [\color{red}{3}, 3, \color{blue}{2}, 2] \to [2, \color{red}{3}, 2, \color{blue}{2}] \to [2, 2, 2, 2]$。 这里红色数字是 $ i $ 索引（将被赋值），蓝色数字是 $ j $ 索引。