← 返回题目列表

AtCoder · awc0030_e

E. 优化团队划分

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

分数: 466 分

问题陈述

高桥被分配了将编程训练营的参与者分成小组的任务。

有 N 训练营的参与者,以及训练营的技能水平 i第参与者 (1 \leq i \leq N) is A_i。高桥会选择 1 或更多参与者 N 人要形成准确 1 团队。每个参与者要么被选择,要么不被选择,并且同一参与者不能被选择多次。未入选的参赛者将不参加本次团队活动。

团队的“凝聚力”定义如下:

  • 所有选定团队成员的技能水平的最大公约数 (GCD) 乘以团队成员数量。

也就是说,如果 k 人 (k \geq 1) 选自 N 参与者,所选成员的技能水平为 B_1, B_2, \ldots, B_k,则内聚力为

\gcd(B_1, B_2, \ldots, B_k) \times k

在这里,当 k = 1,我们定义 \gcd(B_1) = B_1.

求高桥最优选择时凝聚力的最大值。

约束

  • 1 \leq N \leq 10^6
  • 1 \leq A_i \leq 10^6
  • 的 A_i 不一定是不同的。
  • 所有输入值均为整数。

输入

N
A_1 A_2 \ldots A_N
  • 第一行包含一个正整数 N,代表参与者数量。
  • 第二行包含 N 正整数 A_1, A_2, \ldots, A_N 以空格分隔,代表每个参与者的技能水平。

输出

在单行中打印内聚力的最大值。


示例输入 1

5
2 3 4 6 9

示例输出 1

9

示例输入 2

4
5 10 15 20

示例输出 2

20

示例输入 3

10
12 18 24 36 48 6 30 60 42 54

示例输出 3

60

示例输入 4

20
100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000

示例输出 4

2000

示例输入 5

1
1000000

示例输出 5

1000000