Divan and Kostomuksha (hard version)

题意翻译

给定一个序列 $a$ ，定义其权值为： $$ \sum_{i=1}^n\gcd(a_1,a_2,...,a_i) $$ 现在你可以重排 $a$ ，求这个权值的最大值。 **本题与同场 D1 的唯一差别在于 $a_i$ 的范围。**

题目描述

This is the hard version of the problem. The only difference is maximum value of $ a_i $ . Once in Kostomuksha Divan found an array $ a $ consisting of positive integers. Now he wants to reorder the elements of $ a $ to maximize the value of the following function: $ $\sum_{i=1}^n \operatorname{gcd}(a_1, \, a_2, \, \dots, \, a_i), $ $ where $ \\operatorname{gcd}(x\_1, x\_2, \\ldots, x\_k) $ denotes the <a href="https://en.wikipedia.org/wiki/Greatest_common_divisor">greatest common divisor</a> of integers $ x\_1, x\_2, \\ldots, x\_k $ , and $ \\operatorname{gcd}(x) = x $ for any integer $ x$. Reordering elements of an array means changing the order of elements in the array arbitrary, or leaving the initial order. Of course, Divan can solve this problem. However, he found it interesting, so he decided to share it with you.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \leq n \leq 10^5 $ ) — the size of the array $ a $ . The second line contains $ n $ integers $ a_{1}, \, a_{2}, \, \dots, \, a_{n} $ ( $ 1 \le a_{i} \le 2 \cdot 10^7 $ ) — the array $ a $ .

输出格式

Output the maximum value of the function that you can get by reordering elements of the array $ 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

说明

In the first example, it's optimal to rearrange the elements of the given array in the following order: $ [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. $ $ It can be shown that it is impossible to get a better answer.</p><p>In the second example, it's optimal to rearrange the elements of a given array in the following order: $ \[100, \\, 10, \\, 10, \\, 5, \\, 1, \\, 3, \\, 3, \\, 7, \\, 42, \\, 54\]$.

题意翻译

给定一个序列 $a$ ，定义其权值为： $$ \sum_{i=1}^n\gcd(a_1,a_2,...,a_i) $$ 现在你可以重排 $a$ ，求这个权值的最大值。 **本题与同场 D1 的唯一差别在于 $a_i$ 的范围。**