Ela and Prime GCD

题目描述

After a long, tough, but fruitful day at DTL, Ela goes home happily. She entertains herself by solving Competitive Programming problems. She prefers short statements, because she already read too many long papers and documentation at work. The problem of the day reads:You are given an integer $ c $ . Suppose that $ c $ has $ n $ divisors. You have to find a sequence with $ n - 1 $ integers $ [a_1, a_2, ... a_{n - 1}] $ , which satisfies the following conditions: - Each element is strictly greater than $ 1 $ . - Each element is a divisor of $ c $ . - All elements are distinct. - For all $ 1 \le i < n - 1 $ , $ \gcd(a_i, a_{i + 1}) $ is a prime number. In this problem, because $ c $ can be too big, the result of prime factorization of $ c $ is given instead. Note that $ \gcd(x, y) $ denotes the greatest common divisor (GCD) of integers $ x $ and $ y $ and a prime number is a positive integer which has exactly $ 2 $ divisors.

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) - the number of test cases. The first line of each test case contains one integer $ m $ ( $ 1 \le m \le 16 $ ) - the number of prime factor of $ c $ . The second line of each test case contains $ m $ integers $ b_1, b_2, \ldots, b_m $ ( $ 1 \le b_i < 2^{20} $ ) — exponents of corresponding prime factors of $ c $ , so that $ c = p_1^{b_1} \cdot p_2^{b_2} \cdot \ldots \cdot p_m^{b_m} $ and $ n = (b_1 + 1)(b_2 + 1) \ldots (b_m + 1) $ hold. $ p_i $ is the $ i $ -th smallest prime number. It is guaranteed that the sum of $ n \cdot m $ over all test cases does not exceed $ 2^{20} $ .

输出格式

Print the answer for each test case, one per line. If there is no sequence for the given $ c $ , print $ -1 $ . Otherwise, print $ n - 1 $ lines. In $ i $ -th line, print $ m $ space-separated integers. The $ j $ -th integer of $ i $ -th line is equal to the exponent of $ j $ -th prime number from $ a_i $ . If there are multiple answers, print any of them.

输入输出样例

输入样例 #1

5
2
1 1
1
1
3
1 1 1
1
4
2
2 1

输出样例 #1

0 1 
1 1 
1 0 
1 
0 1 1 
0 0 1 
1 0 1 
1 1 0 
0 1 0 
1 1 1 
1 0 0 
-1
2 0 
1 1 
0 1 
2 1 
1 0

说明

In each test case, the values of $ c $ are $ 6 $ , $ 2 $ , $ 30 $ , $ 16 $ , and $ 12 $ in that order. In the first test case, $ 1 $ , $ 2 $ , $ 3 $ , $ 6 $ are divisors of $ 6 $ . Here, sequences $ [2, 6, 3] $ and $ [3, 6, 2] $ can be answer. Permutation $ [3, 2, 6] $ is invalid because $ \gcd(a_1, a_2) = 1 $ is not a prime number. In the forth test case, $ 1 $ , $ 2 $ , $ 4 $ , $ 8 $ , $ 16 $ are divisors of $ 16 $ . Among the permutation of sequence $ [2, 4, 8, 16] $ , no valid answer exist.

**题目描述**

在辛苦而又充实的一天结束后，Ela高兴地回家，并通过解决竞技编程问题来娱乐自己。她喜欢简短的题目描述，因为在工作中她已经阅读了太多的长论文和文档。当天的问题是：给你一个整数$ c $。假设$ c $有$ n $个除数。你必须找到一个序列，包含$ n - 1 $个整数$ [a_1, a_2, ... a_{n - 1}] $，满足以下条件：

- 每个元素严格大于1。
- 每个元素都是$ c $的除数。
- 所有元素都是不同的。
- 对于所有$ 1 \le i < n - 1 $，$ \gcd(a_i, a_{i + 1}) $是一个素数。

在这个问题中，因为$ c $可能非常大，所以给出$ c $的质因数分解结果。注意，$ \gcd(x, y) $表示整数$ x $和$ y $的最大公约数（GCD），素数是正好有2个除数的正整数。

**输入输出格式**

**输入格式**

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

每个测试用例的第一行包含一个整数$ m $（$ 1 \le m \le 16 $）——$ c $的素因子数量。

每个测试用例的第二行包含$ m $个整数$ b_1, b_2, \ldots, b_m $（$ 1 \le b_i < 2^{20} $）——对应素因子的指数，使得$ c = p_1^{b_1} \cdot p_2^{b_2} \cdot \ldots \cdot p_m^{b_m} $和$ n = (b_1 + 1)(b_2 + 1) \ldots (b_m + 1) $成立。$ p_i $是第$ i $个最小的素数。

保证所有测试用例的$ n \cdot m $之和不超过$ 2^{20} $。

**输出格式**

为每个测试用例打印一行答案。如果没有给定$ c $的序列，打印$ -1 $。

否则，打印$ n - 1 $行。在第$ i $行中，打印$ m $个空格分隔的整数。第$ i $行的第$ j $个整数等于$ a_i $中第$ j $个素数的指数。

如果有多个答案，打印其中任何一个。

**输入输出样例**

**输入样例 #1**
```
5
2
1 1
1
1
3
1 1 1
1
4
2
2 1
```

**输出样例 #1**
```
0 1
1 1
1 0
1
0 1 1
0 0 1
1 0 1
1 1 0
0 1 0
1 1 1
1 0 0
-1
2 0
1 1
0 1
2 1
1 0
```

**说明**

在每个测试用例中，$ c $的值依次为$ 6 $，$ 2 $，$ 30 $，$ 16 $，$ 12 $。

在第一个测试用例中，$ 1 $，$ 2 $，$ 3 $，$ 6 $是6的除数。这里，序列$ [2, 6, 3] $和$ [3, 6, 2] $可以是答案。排列$ [3, 2, 6] $是无效的，因为$ \gcd(a_1, a_2) = 1 $不是一个素数。

在第四个测试用例中，$ 1 $，$ 2 $，$ 4 $，$ 8 $，$ 16 $是16的除数。在序列$ [2, 4, 8, 16] $的排列中，没有有效的答案存在。**题目描述** 在辛苦而又充实的一天结束后，Ela高兴地回家，并通过解决竞技编程问题来娱乐自己。她喜欢简短的题目描述，因为在工作中她已经阅读了太多的长论文和文档。当天的问题是：给你一个整数$ c $。假设$ c $有$ n $个除数。你必须找到一个序列，包含$ n - 1 $个整数$ [a_1, a_2, ... a_{n - 1}] $，满足以下条件： - 每个元素严格大于1。 - 每个元素都是$ c $的除数。 - 所有元素都是不同的。 - 对于所有$ 1 \le i < n - 1 $，$ \gcd(a_i, a_{i + 1}) $是一个素数。 在这个问题中，因为$ c $可能非常大，所以给出$ c $的质因数分解结果。注意，$ \gcd(x, y) $表示整数$ x $和$ y $的最大公约数（GCD），素数是正好有2个除数的正整数。 **输入输出格式** **输入格式** 第一行包含一个整数$ t $（$ 1 \le t \le 10^4 $）——测试用例的数量。 每个测试用例的第一行包含一个整数$ m $（$ 1 \le m \le 16 $）——$ c $的素因子数量。 每个测试用例的第二行包含$ m $个整数$ b_1, b_2, \ldots, b_m $（$ 1 \le b_i < 2^{20} $）——对应素因子的指数，使得$ c = p_1^{b_1} \cdot p_2^{b_2} \cdot \ldots \cdot p_m^{b_m} $和$ n = (b_1 + 1)(b_2 + 1) \ldots (b_m + 1) $成立。$ p_i $是第$ i $个最小的素数。 保证所有测试用例的$ n \cdot m $之和不超过$ 2^{20} $。 **输出格式** 为每个测试用例打印一行答案。如果没有给定$ c $的序列，打印$ -1 $。 否则，打印$ n - 1 $行。在第$ i $行中，打印$ m $个空格分隔的整数。第$ i $行的第$ j $个整数等于$ a_i $中第$ j $个素数的指数。 如果有多个答案，打印其中任何一个。 **输入输出样例** **输入样例 #1** ``` 5 2 1 1 1 1 3 1 1 1 1 4 2 2 1 ``` **输出样例 #1** ``` 0 1 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 0 0 1 0 1 1 1 1 0 0 -1 2 0 1 1 0 1 2 1 1 0 ``` **说明** 在每个测试用例中，$ c $的值依次为$ 6 $，$ 2 $，$ 30 $，$ 16 $，$ 12 $。 在第一个测试用例中，$ 1 $，$ 2 $，$ 3 $，$ 6 $是6的除数。这里，序列$ [2, 6, 3] $和$ [3, 6, 2] $可以是答案。排列$ [3, 2, 6] $是无效的，因为$ \gcd(a_1, a_2) = 1 $不是一个素数。 在第四个测试用例中，$ 1 $，$ 2 $，$ 4 $，$ 8 $，$ 16 $是16的除数。在序列$ [2, 4, 8, 16] $的排列中，没有有效的答案存在。