| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 69 | 44 | 43 | 65.152% |
There are $N$ cards in a deck, numbered from 1ドル$ to $N,ドル where card $i$ has a positive integer $A_i$ written on it.
You are to perform $N - 1$ moves with the cards. In each move, you select two cards of your choice from the deck. Let $x$ and $y$ be the integers written on the selected cards, respectively. Remove both selected cards, and insert a new card into the deck with 2ドル \cdot \gcd(x, y)$ written on it, where $\gcd(x, y)$ is the greatest common divisor of $x$ and $y$. Note that with this one move, there will be one fewer card in the deck (as you remove two cards and insert one new card).
After all $N -1$ moves have been performed, there will be exactly one card remaining. Your goal is to maximize the integer written on the last card; output this integer.
Input begins with an integer $N$ (2ドル ≤ N ≤ 100,円 000$) representing the number of cards. The next line contains $N$ integers $A_i$ (1ドル ≤ A_i ≤ 10^9$) representing the number written on card $i$.
Output an integer in a single line representing the maximum possible integer written on the last card.
3 2 4 6
8
To get the maximum possible integer on the last card, you have to select card 1ドル$ and card 3ドル$ on the first move with $x = 2$ and $y = 6$. Remove both selected cards, and insert a new card with 2ドル \cdot \gcd(2, 6) = 4$ written on it. For the second move, there are two cards remaining with an integer 4ドル$ written on each card. Select those cards with $x = 4$ and $y = 4$. Remove both selected cards, and insert a new card with 2ドル \cdot \gcd(4, 4) = 8$ written on it. The last card has an integer 8ドル$ written on it, and it is the maximum possible integer in this example.
3 3 5 7
2
Regardless of your choice in each move, the answer will always be 2ドル$.
4 9 9 9 9
36
5 10 100 1000 10000 100000
160