Это сложная версия задачи. Единственным различием между версиями является ограничение на \(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 может решить эту задачу сам. Однако он посчитал, что она достаточно интересная, чтобы поделиться ею с вами.
Примечание
В первом примере можно расположить элементы массива в следующем порядке: \([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]\).