← 返回题目列表

Codeforces · 1614/D1

D1. Divan 和 Kostomuksha(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。唯一的区别是 $$$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]$$$。