Это сложная версия задачи. Различия между версиями заключаются в ограничениях на \(m\). Вы можете делать взломы, только если обе версии задачи сданы.
Вам дан массив \(a\) длины \(n\) и два целых числа \(m\) и \(k\). Каждый элемент в \(a\) удовлетворяет условию \(1\le a_i \le m\).
За одну операцию вы выбираете два индекса \(i\) и \(j\) такие, что \(1 \le i < j \le |a|\), затем добавляете \(\gcd(a_i,a_j)\) в конец массива и удаляете \(a_i\) и \(a_j\) из массива. Обратите внимание, что после этой операции длина массива уменьшится на единицу.
Найдите максимально возможную сумму массива после выполнения ровно \(k\) операций.
Первая строка содержит одно целое число \(t\) (\(1\le t\le 10^5\)) — количество наборов входных данных. Далее следует описание наборов.
Первая строка каждого набора содержит три целых числа \(n\), \(m\) и \(k\) (\(2 \le n \le 10^6\); \(1\le m \le 9\cdot 10^{18}\); \(1 \le k \le n-1\)).
Вторая строка каждого набора входных данных содержит \(n\) целых чисел \(a_1,a_2,\ldots,a_n\) (\(1 \le a_i \le m\)).
Гарантируется, что сумма \(n\) по всем наборам не превышает \(10^6\).
Для каждого набора входных данных выведите максимально возможную сумму массива после оптимального выполнения \(k\) операций.
В первом наборе входных данных лучшим способом является выбор \(i=1\), \(j=3\) в первой операции. Итоговая последовательность — \([7,4]\).
4 3 8 1 4 7 8 5 114514 2 7 2 4 1 6 3 1919810 2 2 3 3 3 9000000000000000000 1 9000000000000000000 9000000000000000000 9000000000000000000
11 14 1 18000000000000000000
3000 ms 1024 Mb Правила оформления программ и список ошибок при автоматической проверке задач