Дан полный граф с $$$n$$$ вершинами, где $$$i$$$-я вершина имеет вес $$$p_i$$$. Вес ребра, соединяющего вершину $$$x$$$ и вершину $$$y$$$, равен $$$\operatorname{max}(p_x, p_y) \bmod \operatorname{min}(p_x, p_y)$$$.
Найдите минимальный суммарный вес $$$n - 1$$$ ребер, которые образуют одну компоненту связности размера $$$n$$$ в этом графе.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$).
Следующая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le 5 \cdot 10^5$$$).
Гарантируется, что сумма $$$n$$$ по всем входным данным не превышает $$$5 \cdot 10^5$$$.
Гарантируется, что сумма $$$\max(p_1,p_2,\ldots,p_n)$$$ по всем входным данным не превышает $$$5 \cdot 10^5$$$.
Для каждого набора входных данных выведите ровно одно число — вес минимального остовного дерева.
454 3 3 4 4102 10 3 2 9 9 4 6 4 61233 56 48 41 89 73 99 150 55 100 111 130711 45 14 19 19 8 10
1 0 44 10
В первом наборе входных данных один из возможных способов соединить ребра — провести ребра $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(1, 5)$$$, $$$(2, 3)$$$. Вес первого ребра равен $$$\operatorname{max}(p_1, p_2) \bmod \operatorname{min}(p_1, p_2)=4 \bmod 3 = 1$$$, а вес всех остальных ребер $$$0$$$.
| Codeforces Round 1010 (Div. 1, Unrated) |
|---|
| Закончено |
