CF2227C Snowfall

Yousef 给了你一个长度为 $n$ 的正整数数组 $a$。 定义 $f(a)$ 表示 $a$ 的所有子数组中，元素乘积能被 $6$ 整除的子数组的数量。 更具体地说，对于每对下标 $l$ 和 $r$，满足 $1 \le l \le r \le n$，考虑子数组 $a_l, a_{l+1}, \dots, a_r$。如果该子数组的元素乘积能被 $6$ 整除，则计入 $f(a)$。 例如，若 $a = [1, 6, 2]$，则乘积能被 $6$ 整除的子数组为 $[6]$、$[1, 6]$、$[6, 2]$ 以及 $[1, 6, 2]$，因此 $f(a) = 4$。 你的任务是重新排列数组 $a$ 的元素，使得 $f(a)$ 最小。如果有多种方式满足条件，你可以输出任意一种。 注意：$^\ast$ 当数组 $b$ 可以通过从数组 $a$ 的开头和末尾各删除零个或若干个元素得到时，$b$ 被称为 $a$ 的子数组。

输入第一行为一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例的数量。 每个测试用例的第一行为一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——数组的长度。 接下来一行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）——数组的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试数据，输出重新排列后的数组 $a$，使 $f(a)$ 最小。如果有多种答案，可以输出任意一种。

在第一个测试用例中，一种最优的排列是 $a = [12, 18, 4, 7, 5, 9]$。其中乘积能被 $6$ 整除的子数组为： - $[12]$ - $[18]$ - $[12, 18]$ - $[18, 4]$ - $[12, 18, 4]$ - $[18, 4, 7]$ - $[12, 18, 4, 7]$ - $[18, 4, 7, 5]$ - $[4, 7, 5, 9]$ - $[12, 18, 4, 7, 5]$ - $[18, 4, 7, 5, 9]$ - $[12, 18, 4, 7, 5, 9]$ 因此 $f(a) = 12$。可以证明不存在更优的排列使得 $f(a)$ 更小。 由 ChatGPT 5 翻译