B - Sum + GCD (Easy)
Assam
2
s
1024
MB
200
点
問題文
長さ $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
2
$A_2$ または $A_4$ のみを選ぶと $S=1$ 、 $G=1$ 、 $S+G=2$ になります。これが最小なので $2$ を出力してください。
入力例 2
2
100 100
出力例 2
200
$A_1$ または $A_2$ のみを選ぶのが最適です。
入力例 3
3
100 50 1
出力例 3
2
$A_3$ のみを選ぶことで、$S + G = 2$ となります。