分数: 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