Сума НСД
Обмеження: 2 сек., 256 МіБ
Задано масив \(a\) з \(n\) елементів. Потрібно розбити його на дві непорожні підмножини \(b\) і \(c\) так, щоб максимізувати НСД(\(b\)) + НСД(\(c\)). Кожен елемент масиву повинен належати рівно одній з підмножин.
НСД масиву — це найбільше ціле число таке, що всі елементу цього масиву діляться на це число.
Вхідні дані
У першому рядку задано одне ціле число \(n\) — розмір масиву.
У другому рядку задано \(n\) цілих чисел \(a_i\).
Вихідні дані
У єдиному рядку виведіть одне ціле число — максимальне значення НСД(\(b\)) + НСД(\(c\)).
Обмеження
\(2 \le n \le 10^5\),
\(1 \le a_i \le 10^9\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
4 4 4 7 6 | 9 |
Джерело: Відбір 2019 - День 4
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|