Codeforces Round 973 (Div. 2) |
---|
Закончено |
Так как Мансур устал делать легенды, легенды на эту задачу не будет.
Дан массив натуральных чисел $$$a_1, a_2, \ldots, a_n$$$. В нём можно переставить элементы произвольным образом. Требуется узнать минимально возможное значение выражения $$$$$$\gcd(a_1) + \gcd(a_1, a_2) + \ldots + \gcd(a_1, a_2, \ldots, a_n),$$$$$$ где $$$\gcd(a_1, a_2, \ldots, a_n)$$$ обозначает наибольший общий делитель (НОД) чисел $$$a_1, a_2, \ldots, a_n$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное число $$$n$$$ ($$$1 \le n \le 10^5$$$) — размер массива.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — исходный массив.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$.
Гарантируется, что сумма $$$\max(a_1, a_2, \ldots, a_n)$$$ по всем наборам входных данных не превышает $$$10^5$$$.
Для каждого набора входных данных выведите единственное число в отдельной строке — ответ на задачу.
534 2 226 3310 15 656 42 12 52 20442 154 231 66
6 6 9 14 51
В первом наборе входных данных можно переставить элементы следующим образом: $$$[2, 4, 2]$$$, тогда ответом будет $$$\gcd(2) + \gcd(2, 4) + \gcd(2, 4, 2) = 2 + 2 + 2 = 6$$$.
В третьем наборе входных данных можно переставить элементы следующим образом: $$$[6, 10, 15]$$$, тогда ответом будет $$$\gcd(6) + \gcd(6, 10) + \gcd(6, 10, 15) = 6 + 2 + 1 = 9$$$.
Название |
---|