思路

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

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	if (!(cin >> n)) return 0;
	vector<int> cnt(13, 0);
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	// 结果序列
	vector<int> ans;
	ans.reserve(n);

	// 选取当前未用元素中的最大值作为开头
	int cur = 0;
	for (int v = 12; v >= 1; --v) {
		if (cnt[v]) {
			cur = v;
			cnt[v]--;
			ans.push_back(v);
			break;
		}
	}

	// 逐步选择使 gcd(cur, x) 最大的元素（并列取值更大者）
	for (int used = 1; used < n; ++used) {
		int bestG = -1, pick = -1;
		for (int v = 12; v >= 1; --v) {
			if (!cnt[v]) continue;
			int g = std::gcd(cur, v);
			if (g > bestG || (g == bestG && v > pick)) {
				bestG = g;
				pick = v;
			}
		}
		// 放入选择的元素，更新当前前缀 gcd
		cnt[pick]--;
		cur = std::gcd(cur, pick);
		ans.push_back(pick);
	}

	// 输出
	for (int i = 0; i < n; ++i) {
		if (i) cout << ' ';
		cout << ans[i];
	}
	cout << '\n';
	return 0;
}

Python

import sys
import math

def solve():
	data = sys.stdin.read().strip().split()
	if not data:
		return
	it = iter(data)
	n = int(next(it))
	cnt = [0] * 13
	arr = [int(next(it)) for _ in range(n)]
	for x in arr:
		cnt[x] += 1

	ans = []

	# 选取当前未用元素中的最大值作为开头
	cur = 0
	for v in range(12, 0, -1):
		if cnt[v]:
			cur = v
			cnt[v] -= 1
			ans.append(v)
			break

	# 每次选择使 gcd(cur, x) 最大的元素（并列取值更大）
	for _ in range(1, n):
		bestG, pick = -1, -1
		for v in range(12, 0, -1):
			if cnt[v] == 0:
				continue
			g = math.gcd(cur, v)
			if g > bestG or (g == bestG and v > pick):
				bestG, pick = g, v
		cnt[pick] -= 1
		cur = math.gcd(cur, pick)
		ans.append(pick)

	print(' '.join(map(str, ans)))

if __name__ == "__main__":
	solve()

Java

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner(System.in);
		int n = fs.nextInt();
		int[] cnt = new int[13];
		for (int i = 0; i < n; i++) {
			int x = fs.nextInt();
			cnt[x]++;
		}

		StringBuilder sb = new StringBuilder();
		List<Integer> ans = new ArrayList<>(n);

		// 选取当前未用元素中的最大值作为开头
		int cur = 0;
		for (int v = 12; v >= 1; v--) {
			if (cnt[v] > 0) {
				cur = v;
				cnt[v]--;
				ans.add(v);
				break;
			}
		}

		// 每步选择使 gcd(cur, x) 最大的元素（并列取值更大）
		for (int used = 1; used < n; used++) {
			int bestG = -1, pick = -1;
			for (int v = 12; v >= 1; v--) {
				if (cnt[v] == 0) continue;
				int g = gcd(cur, v);
				if (g > bestG || (g == bestG && v > pick)) {
					bestG = g;
					pick = v;
				}
			}
			cnt[pick]--;
			cur = gcd(cur, pick);
			ans.add(pick);
		}

		for (int i = 0; i < ans.size(); i++) {
			if (i > 0) sb.append(' ');
			sb.append(ans.get(i));
		}
		System.out.println(sb.toString());
	}

	static int gcd(int a, int b) {
		while (b != 0) {
			int t = a % b;
			a = b;
			b = t;
		}
		return a;
	}

	// 轻量读入
	static class FastScanner {
		BufferedInputStream in;
		byte[] buffer = new byte[1 << 16];
		int ptr = 0, len = 0;
		FastScanner(InputStream is) { in = new BufferedInputStream(is); }
		private int read() throws IOException {
			if (ptr >= len) {
				len = in.read(buffer);
				ptr = 0;
				if (len <= 0) return -1;
			}
			return buffer[ptr++];
		}
		int nextInt() throws IOException {
			int c, sgn = 1, x = 0;
			do { c = read(); } while (c <= 32);
			if (c == '-') { sgn = -1; c = read(); }
			while (c > 32) {
				x = x * 10 + (c - '0');
				c = read();
			}
			return x * sgn;
		}
	}
}

题目内容

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$ 。可以证明这是最大能达到的值。