CF1407B Big Vova

Alexander 是一位著名的程序员。今天他终于决定出门踢足球，但第一次射门就把富商 Big Vova 的新劳斯莱斯撞出了一个坑。Vladimir 最近在热门线上商城“Zmey-Gorynych”开了一家店，并向 Alex 提供了一份工作：如果他能通过解决一道编程题展示自己的能力，就能成为网络安全专家。否则，他将在接下来的两年里为其送一些可疑的商品。 给定 $n$ 个正整数 $a_1, a_2, \dots, a_n$。你需要用它们每个恰好一次，构造一个序列 $b_1, b_2, \dots, b_n$，使得序列 $c_1, c_2, \dots, c_n$ 在字典序上最大，其中 $c_i = \gcd(b_1, \dots, b_i)$，即 $b$ 的前 $i$ 个元素的最大公约数。 Alexander 对这道简单题的条件感到非常害怕，于是请求你帮他解决。 如果序列 $a$ 在字典序上小于序列 $b$，当且仅当满足以下条件之一： - $a$ 是 $b$ 的前缀，且 $a \ne b$； - 在第一个不同的位置，$a$ 的元素小于 $b$ 对应位置的元素。

每个测试点包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^3$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^3$），表示序列 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, \dots, a_n$（$1 \le a_i \le 10^3$），表示序列 $a$。 保证所有测试用例中 $n$ 的总和不超过 $10^3$。

对于每个测试用例，输出一行答案，即所需的序列 $b$。如果有多种答案，输出任意一种即可。

在第一个样例中，只有两种排列 $b$——$[2, 5]$ 和 $[5, 2]$：对于第一个排列，$c=[2, 1]$，对于第二个排列，$c=[5, 1]$。 在第三个样例中，数字 $9$ 应该排在 $b$ 的第一个位置，且 $GCD(9, 3)=3$，$GCD(9, 8)=1$，所以 $b$ 的第二个数字应该是 $3$。 在第七个样例中，前四个数字两两之间有一个公因数（2 的幂），但在最优排列 $b$ 中，没有一个数字可以作为第一个。 由 ChatGPT 4.1 翻译