Сума НСД
Limits: 2 sec., 256 MiB
Задано масив \(a\) з \(n\) елементів. Потрібно розбити його на дві непорожні підмножини \(b\) і \(c\) так, щоб максимізувати НСД(\(b\)) + НСД(\(c\)). Кожен елемент масиву повинен належати рівно одній з підмножин.
НСД масиву — це найбільше ціле число таке, що всі елементу цього масиву діляться на це число.
Input
У першому рядку задано одне ціле число \(n\) — розмір масиву.
У другому рядку задано \(n\) цілих чисел \(a_i\).
Output
У єдиному рядку виведіть одне ціле число — максимальне значення НСД(\(b\)) + НСД(\(c\)).
Constraints
\(2 \le n \le 10^5\),
\(1 \le a_i \le 10^9\).
Samples
Input (stdin) | Output (stdout) |
---|---|
4 4 4 7 6 | 9 |
Source: Відбір 2019 - День 4
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|