65 lines
1.9 KiB
Markdown
65 lines
1.9 KiB
Markdown
# CF1614D2 Divan and Kostomuksha (hard version)
|
||
|
||
## 题目描述
|
||
|
||
这是该问题的困难版本。唯一的区别在于 $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_1, x_2, \ldots, x_k$ 的[最大公约数](https://en.wikipedia.org/wiki/Greatest_common_divisor)，且对于任意整数 $x$，有 $\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 2 \cdot 10^7$）——数组 $a$。
|
||
|
||
## 输出格式
|
||
|
||
输出通过重新排列数组 $a$ 后可以获得的该函数的最大值。
|
||
|
||
## 输入输出样例 #1
|
||
|
||
### 输入 #1
|
||
|
||
```
|
||
6
|
||
2 3 1 2 6 2
|
||
```
|
||
|
||
### 输出 #1
|
||
|
||
```
|
||
14
|
||
```
|
||
|
||
## 输入输出样例 #2
|
||
|
||
### 输入 #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]$。
|
||
|
||
由 ChatGPT 4.1 翻译 |