60. Johnny Johnny

0 Judge

Code: 0


題目

Johnny Johnny 的爸爸有$n$個兒子:一郎、二郎、....、n-1郎和Johnny Johnny。這些小孩都很愛吃糖,第$i$個小孩想吃到的糖果數量用 $a_i$ 來表示。

但是爸爸不想讓他們吃太多糖,所以爸爸就訂了一條規則:

爸爸會選出$m\ (m\leq n 且 m \geq 2)$ 個人,再將這$m$個小孩每個人想吃的數量 $a_i$ 取最最大公因數,

得到的數字即為所有小孩能吃到的糖果總數。

example:

有5個小孩,他們想吃到的糖果數量分別是

一郎:1顆,
二郎:4顆,
三郎:6顆,
四郎:9顆,
Johnny Johnny:18顆

如果爸爸選擇一郎、二郎、Johnny Johnny,那他們拿到的糖果數為

GCD(1, 4, 18) = 1

如果爸爸選擇四郎、Johnny Johnny,那他們拿到的糖果數為

GCD(9, 18) = 9 將會是最大值

幫幫Johnny Johnny計算他們可能可以吃到的糖果數量的最大值?

測資 範圍
0 同範測
1 $2\leq n \leq 10, \ 1\leq a_i \leq 10^9$
2 $2 \leq n \leq 10, \ 1\leq a_i \leq 10^9$
3 $2 \leq n \leq 1000, \ 1\leq a_i \leq 10^9$
4 $2\leq n \leq 2000, \ 1\leq a_i \leq 10^9$
5 $2\leq n\leq2000, \ 1\leq a_i \leq 10^9$

input

輸入分成兩行

第一行會輸入 $n\ (2\leq n\leq 2000)$

第二行會輸入$n$ 個數字$a_1$ ~ $a_n$ ($1\leq a_i \leq 10^9$)

output

輸出只包含一個數字,他們能夠吃到的最多糖果數

記得在輸出結尾輸出\n

sample input

5
1 4 6 9 18

sample output

9

沒有甚麼用的補充資料

https://www.youtube.com/watch?v=j4_Dojdej2Q


Judge Setting

run-time limit: 1000 ms
memory limit: 1048576 byte
測資數量: 6