题目内容

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)$

思路

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

C++