CF1737F Ela and Prime GCD

在 DTL 度过了漫长、艰难但充实的一天后，Ela 开心地回家了。她通过解答竞赛编程题目来娱乐自己。她更喜欢题面简短的题目，因为她在工作中已经读了太多冗长的论文和文档。今天的题目如下： 给定一个整数 $c$。假设 $c$ 有 $n$ 个约数。你需要找到一个长度为 $n-1$ 的整数序列 $[a_1, a_2, \ldots, a_{n-1}]$，满足以下条件： - 每个元素都严格大于 $1$。 - 每个元素都是 $c$ 的约数。 - 所有元素互不相同。 - 对于所有 $1 \le i < n-1$，都有 $\gcd(a_i, a_{i+1})$ 是质数。 在本题中，因为 $c$ 可能非常大，题目直接给出了 $c$ 的质因数分解结果。注意，$\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数，质数是恰好有 $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$ 小的质数。 保证所有测试用例中 $\sum n \cdot m \le 2^{20}$。

对于每个测试用例，输出一组答案，每行一个。如果不存在满足条件的序列，输出 $-1$。 否则，输出 $n-1$ 行。第 $i$ 行输出 $m$ 个用空格分隔的整数，第 $j$ 个整数表示 $a_i$ 中第 $j$ 个质数的指数。 如果有多组答案，输出任意一组均可。

每个测试用例中，$c$ 的值依次为 $6$、$2$、$30$、$16$ 和 $12$。 在第一个测试用例中，$6$ 的约数为 $1$、$2$、$3$、$6$。此时，序列 $[2, 6, 3]$ 和 $[3, 6, 2]$ 都是合法答案。排列 $[3, 2, 6]$ 不合法，因为 $\gcd(a_1, a_2) = 1$ 不是质数。 在第四个测试用例中，$16$ 的约数为 $1$、$2$、$4$、$8$、$16$。在 $[2, 4, 8, 16]$ 的所有排列中，没有合法答案。 由 ChatGPT 4.1 翻译