这是问题的简单版本。唯一的区别是 $$$a_i$$$ 的最大值。
在 Kostomuksha Divan 中发现一个由正整数组成的数组 $$$a$$$。现在他想要对 $$$a$$$ 的元素重新排序,以最大化以下函数的值: $$$$$$\sum_{i=1}^n \operatorname{gcd}(a_1, \, a_2, \, \dots, \, a_i),$$$$$$ 其中 $$$\operatorname{gcd}(x_1, x_2, \ldots, x_k)$$$ 表示最大对于任何整数 $$$x$$$,整数的公约数 $$$x_1、x_2、\ldots、x_k$$$ 和 $$$\operatorname{gcd}(x) = x$$$。
对数组元素重新排序意味着任意更改数组中元素的顺序,或保留初始顺序。
Divan当然可以解决这个问题。不过,他觉得这很有趣,所以他决定与大家分享。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 数组 $$$a$$$ 的大小。
第二行包含 $$$n$$$ 整数 $$$a_{1}, \, a_{2}, \, \dots, \, a_{n}$$$ ($$$1 \le a_{i} \le 5 \cdot 10^6$$$) — 数组 $$$a$$$。
输出
输出通过对数组 $$$a$$$ 的元素重新排序可以获得的函数最大值。
示例
输入 #1
6 2 3 1 2 6 2
输出 #1
14
输入 #2
10 5 7 10 3 1 10 100 3 42 54
输出 #2
131
注意
在第一个示例中,最好按以下顺序重新排列给定数组的元素:$$$[6, \, 2, \, 2, \, 2, \, 3, \, 1]$$$:
$$$$$$\operatorname{gcd}(a_1) + \operatorname{gcd}(a_1, \, a_2) + \operatorname{gcd}(a_1, \, a_2, \, a_3) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4, \, a_5) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4, \, a_5, \, a_6) = 6 + 2 + 2 + 2 + 1 + 1 = 14.$$$$$$ 可以证明不可能以获得更好的答案。
在第二个示例中,最好按以下顺序重新排列给定数组的元素:$$$[100, \, 10, \, 10, \, 5, \, 1, \, 3, \, 3, \, 7, \, 42, \, 54]$$$。