思路

• 核心贪心：先取当前未用元素中的最大值作为开头，记当前前缀的 $gcd$ 为 $g$。随后每一步在剩余元素 $x$ 中选取使 $gcd(g,x)$ 最大的那个；若并列，取 $x$ 更大的。选中后令 $g\leftarrow gcd(g,x)$ 并继续，直至使用完所有元素。
• 直觉：让前缀的 $g$ 尽量大、下降尽量慢，可以提升以当前末尾为右端点的所有子数组的 $gcd$ 之和，从而提升总 $S$。该策略会自然把 $1$ 往后推，把具有公共因子的数聚在一起。
• 复杂度：每步在至多$12$种取值中挑选，整体 $O(n\cdot 12)$，满足 $n$ 规模。

C++

题目内容

Tk 有一个长度为 $n$ 的数组 {$a_1,a_2,...,a_n$} 。定义函数 g(i,j) 表示数组从下标 $i$ 到 $j$ 的元素的最大公约数，即 $g(i,j)=gcd(a_i,a_{i+1},...,a_j)$ 。特别低，若 $i=j$，则 $g(i,j)=a_i$ 。

Tk 希望将数组重新打乱排列，使得所有 非空子数组的 $g(i,j)$ 之和尽可能大：

$S=\sum^n_{i=1}\sum^n_{j=1}g(i,j)$

你需要输出一种重新排列后的数组，该排列能使 $S$ 达到最大值。

最大公约数，指多个整数共有约数中最大的一个。例如，$12$ 和 $30$ 的公约数有 $1,2,3,6$ ，其中最大的约数是 $6$ ，因此 $gcd(12,30)=6$ 。

非空子数组 为从原数组中，连续的选择一段元素(可以全选、不可以不选)得到的新数组。

输入描述

第一行输入一个正整数 $n(1≦n≦ 2×10^5)$ ，代表数组的长度。

第二行输入 $n$ 个正整数 $a_1,a_2,...,a_n(1≦a_i≦12)$ ，代表数组的元素。

输出描述

输出一个长度为 $n$ 的数组，代表重新排列后的数组。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

3
2 1 4

输出

2 4 1

说明

在这个样例中，其中一种最优的重新排列后的数组为 {$2,4,1$} ，此时有：

• $g(1,1)=a_1=2$；

• $g(1,2)=gcd(a_1,a_2)=2$；

• $g(1,3)=gcd(a_1,a_2,a_3)=1$；

• $g(2,2)=a_2 = 4$；

• $g(2,3)=gcd(a_2,a_3)=1$；

• $g(3,3)= a_3 = 1$。

总和 $S=2+2+1+4+1+1=11$ 。可以证明这是最大能达到的值。