E - Optimizing Team Division Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は、プログラミング合宿の参加者をチームに分ける係を任されました。

合宿には N 人の参加者がおり、i 番目 (1 \leq i \leq N) の参加者のスキルレベルは A_i です。高橋君はこの N 人の中から 1 人以上の参加者を選んで、ちょうど 1 つのチームを結成します。各参加者は選ばれるか選ばれないかのいずれかであり、同じ参加者を複数回選ぶことはできません。選ばれなかった参加者は今回のチーム活動には参加しません。

チームの「まとまりの良さ」は次のように定義されます：

  • チームに選ばれたメンバー全員のスキルレベルの最大公約数（GCD）に、チームの人数を掛けた値

すなわち、N 人の参加者の中から k 人 (k \geq 1) を選び、選ばれたメンバーのスキルレベルが 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
  • 1 行目には、参加者の人数を表す正整数 N が与えられる。
  • 2 行目には、各参加者のスキルレベルを表す N 個の正整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

まとまりの良さの最大値を 1 行で出力せよ。

入力例 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

Score : 466 pts

Problem Statement

Takahashi has been assigned the task of dividing participants of a programming camp into teams.

There are N participants in the camp, and the skill level of the i-th participant (1 \leq i \leq N) is A_i. Takahashi will select 1 or more participants from these N people to form exactly 1 team. Each participant is either selected or not selected, and the same participant cannot be selected more than once. Participants who are not selected will not participate in this team activity.

The "cohesion" of a team is defined as follows:

  • The greatest common divisor (GCD) of the skill levels of all selected team members, multiplied by the number of team members.

That is, if k people (k \geq 1) are selected from the N participants, and the skill levels of the selected members are B_1, B_2, \ldots, B_k, then the cohesion is

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

Here, when k = 1, we define \gcd(B_1) = B_1.

Find the maximum value of cohesion when Takahashi chooses the selection optimally.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq A_i \leq 10^6
  • The A_i are not necessarily distinct.
  • All input values are integers.

Input

N
A_1 A_2 \ldots A_N
  • The first line contains a positive integer N, representing the number of participants.
  • The second line contains N positive integers A_1, A_2, \ldots, A_N separated by spaces, representing the skill levels of each participant.

Output

Print the maximum value of cohesion in a single line.

Sample Input 1

5
2 3 4 6 9

Sample Output 1

9

Sample Input 2

4
5 10 15 20

Sample Output 2

20

Sample Input 3

10
12 18 24 36 48 6 30 60 42 54

Sample Output 3

60

Sample Input 4

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

Sample Output 4

2000

Sample Input 5

1
1000000

Sample Output 5

1000000