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$ |
輸入分成兩行
第一行會輸入 $n\ (2\leq n\leq 2000)$
第二行會輸入$n$ 個數字$a_1$ ~ $a_n$ ($1\leq a_i \leq 10^9$)
輸出只包含一個數字,他們能夠吃到的最多糖果數
記得在輸出結尾輸出\n
5
1 4 6 9 18
9
https://www.youtube.com/watch?v=j4_Dojdej2Q