D - Sum + GCD (Medium)
Darjeeling
2
s
1024
MB
400
点
問題文
長さ $N$ の正整数列 $A=(A_1, A_2, \ldots, A_N)$ が与えられます。 $A$ から $1$ つ以上の要素を自由に選び、選ばれた要素の総和を $S$ 、選ばれた要素の最大公約数を $G$ とします。$S + G$ の値としてありうる 最大値 を求めてください。
制約
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9\ (1\leq i\leq N)$
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
$N$
$A_1$ $A_2$ $\ldots$ $A_N$
出力
答えを出力せよ。
入力例 1
5
3 1 4 1 5
出力例 1
15
すべて選ぶと $S=14$ 、 $G=1$ 、 $S+G=15$ になります。これが最大なので $15$ を出力してください。
入力例 2
2
1 100
出力例 2
200
$A_2$ のみを選ぶのが最適です。
入力例 3
3
100 50 1
出力例 3
200
$A_1$ のみ、または、$A_1$ と $A_2$ を選ぶことで $S + G = 200$ を達成できます。