解题思路
由于 (ai≤12)，可以把“求所有子数组 gcd 的总和”用经典做法改写为“逐点累加以该点为结尾的所有子数组 gcd 之和”。
对固定序列，令 mp 表示“以当前位置结尾的子数组”的 gcd 统计：
mp[g] = 以当前位置结尾且 gcd 为 g 的子数组个数。
当在末尾追加一个数 (x) 时，新的统计为：
- 把旧的每个 gcd 值 (g) 变成 (gcd(g,x))，计数累加
P3400.第3题-打乱数组排列
题目内容
Tk 有一个长度为 n 的数组 {a1,a2,...,an} 。定义函数 g(i,j) 表示数组从下标 i 到 j 的元素的最大公约数，即 g(i,j)=gcd(ai,ai+1,...,aj) 。特别低，若 i=j，则 g(i,j)=ai 。
Tk 希望将数组重新打乱排列，使得所有 非空子数组的 g(i,j) 之和尽可能大：
S=∑i=1n∑j=1ng(i,j)
你需要输出一种重新排列后的数组，该排列能使 S 达到最大值。
最大公约数，指多个整数共有约数中最大的一个。例如，12 和 30 的公约数有 1,2,3,6 ，其中最大的约数是 6 ，因此 gcd(12,30)=6 。
非空子数组 为从原数组中，连续的选择一段元素(可以全选、不可以不选)得到的新数组。
输入描述
第一行输入一个正整数 n(1≦n≦2×105) ，代表数组的长度。
第二行输入 n 个正整数 a1,a2,...,an(1≦ai≦12) ，代表数组的元素。
输出描述
输出一个长度为 n 的数组，代表重新排列后的数组。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
样例1
输入
3
2 1 4
输出
2 4 1
说明
在这个样例中，其中一种最优的重新排列后的数组为 {2,4,1} ，此时有：
-
g(1,1)=a1=2；
-
g(1,2)=gcd(a1,a2)=2；
-
g(1,3)=gcd(a1,a2,a3)=1；
-
g(2,2)=a2=4；
-
g(2,3)=gcd(a2,a3)=1；
-
g(3,3)=a3=1。
总和 S=2+2+1+4+1+1=11 。可以证明这是最大能达到的值。
