F - GCD Maximum Spanning Tree 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

長さ N の正整数列 A が与えられます。
N 頂点の重み付き完全無向グラフがあります。
各頂点には 1,2,\dots,N の番号が付いています。
1 \leq i \lt j \leq N を満たす i,j について、頂点 i と頂点 j を結ぶ辺の重みは A_i と A_j の最大公約数です。
このグラフの全域木に含まれる辺の重みの総和としてあり得る値の最大値を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq 10^6
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N  
A_1 A_2 \dots A_N

出力

答えを 1 行で出力せよ。

入力例 1

3
4 6 12

出力例 1

10

完全グラフには以下の 3 本の辺が張られています。

  • 頂点 1 と頂点 2 を結ぶ重み 2 の辺
  • 頂点 1 と頂点 3 を結ぶ重み 4 の辺
  • 頂点 2 と頂点 3 を結ぶ重み 6 の辺

2 本目の辺と 3 本目の辺を選ぶと重みの総和は 10 になり、これがあり得る最大値です。

入力例 2

5
5 14 15 21 42

出力例 2

43

入力例 3

2
1 1000000

出力例 3

1

Score : 500 points

Problem Statement

You are given a sequence of positive integers A of length N.
There is a weighted complete undirected graph with N vertices.
The vertices are numbered 1,2,\dots,N.
For i and j satisfying 1 \leq i \lt j \leq N, the weight of the edge connecting vertices i and j is the greatest common divisor of A_i and A_j.
Find the maximum possible value of the sum of the weights of the edges included in a spanning tree of this graph.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq 10^6
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N  
A_1 A_2 \dots A_N

Output

Output the answer in one line.

Sample Input 1

3
4 6 12

Sample Output 1

10

The complete graph has the following three edges.

  • The edge connecting vertices 1 and 2 with weight 2
  • The edge connecting vertices 1 and 3 with weight 4
  • The edge connecting vertices 2 and 3 with weight 6

Choosing the second and third edges gives a sum of weights of 10, which is the maximum possible value.

Sample Input 2

5
5 14 15 21 42

Sample Output 2

43

Sample Input 3

2
1 1000000

Sample Output 3

1