Codeforces Round 757 (Div. 2) |
---|
Закончено |
Это простая версия задачи. Единственным различием между версиями является ограничение на $$$a_i$$$.
Однажды в Костомукше Divan нашел массив $$$a$$$, состоящий из целых положительных чисел! Он хочет каким-нибудь образом переупорядочить элементы массива $$$a$$$ так, чтобы максимизировать следующее выражение: $$$$$$\sum_{i=1}^n \operatorname{gcd}(a_1, \, a_2, \, \dots, \, a_i),$$$$$$ где $$$\operatorname{gcd}(x_1, x_2, \ldots, x_k)$$$ — это наибольший общий делитель чисел $$$x_1, x_2, \ldots, x_k$$$, а $$$\operatorname{gcd}(x) = x$$$ для всех целых чисел $$$x$$$.
Переупорядочить элементы массива означает каким-либо образом поменять порядок элементов в массиве или оставить исходный порядок.
Разумеется, Divan может решить эту задачу сам. Однако он посчитал, что она достаточно интересная, чтобы поделиться ею с вами.
В первой строке находится одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — количество чисел в массиве $$$a$$$.
Вторая строка содержит $$$n$$$ целых чисел $$$a_{1}, \, a_{2}, \, \dots, \, a_{n}$$$ ($$$1 \le a_{i} \le 5 \cdot 10^6$$$) — элементы массива $$$a$$$.
Выведите максимальное значение функции, которое можно получить, переупорядочив элементы массива $$$a$$$.
6 2 3 1 2 6 2
14
10 5 7 10 3 1 10 100 3 42 54
131
В первом примере можно расположить элементы массива в следующем порядке: $$$[6, \, 2, \, 2, \, 2, \, 3, \, 1]$$$. Тогда $$$$$$\operatorname{gcd}(a_1) + \operatorname{gcd}(a_1, \, a_2) + \operatorname{gcd}(a_1, \, a_2, \, a_3) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4, \, a_5) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4, \, a_5, \, a_6) = 6 + 2 + 2 + 2 + 1 + 1 = 14.$$$$$$ Можно показать, что большего ответа для данного массива не существует.
Во втором примере оптимально переупорядочить элементы можно, например, так: $$$[100, \, 10, \, 10, \, 5, \, 1, \, 3, \, 3, \, 7, \, 42, \, 54]$$$.
Название |
---|