← 返回题目列表

Codeforces · 1737/F

F. Ela 和 Prime GCD

中文机器翻译题面 查看原题

在 DTL 度过了漫长、艰难但富有成果的一天后,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$$$ 对应质因数的指数,因此 $$$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]$$$ 的排列中,不存在有效答案。