GCD Master (hard version) (Codeforces 1806F2)
Tags: Math, sortings

This is the hard version of the problem. The only difference between the two versions is the constraint on $$$m$$$. You can make hacks only if both versions of the problem are solved.You are given an array $$$a$$$ of length $$$n$$$ and two integers $$$m$$$ and $$$k$$$. Each element in $$$a$$$ satisfies $$$1\le a_i \le m$$$.In one operation, you choose two indices $$$i$$$ and $$$j$$$ such that $$$1 \le i < j \le |a|$$$, then append $$$\gcd(a_i,a_j)$$$ to the back of the array and delete $$$a_i$$$ and $$$a_j$$$ from the array. Note that the length of the array decreases by one after this operation.Find the maximum possible sum of the array after performing exactly $$$k$$$ operations.

Input: The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^5$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 10^6$$$; $$$1\le m \le 9\cdot 10^{18}$$$; $$$1 \le k \le n-1$$$).The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le m$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case, output the maximum possible sum of the array after performing $$$k$$$ operations optimally.

Note: In the first test case, the best way is to choose $$$i=1$$$, $$$j=3$$$ in the first operation. The final sequence is $$$[7,4]$$$.

Sample Inputs:
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

Sample Outputs:
11
14
1
18000000000000000000

Solution (Python):
from math import gcd
for _ in range(int(input())):
    (N, M, K) = map(int, input().split())
    A = list(map(int, input().split()))
    su = sum(A)
    A.sort()
    (B, C) = ([0], [0])
    for i in range(1, N):
        if A[i] == A[i - 1]:
            B.append(A[i])
    for i in range(1, len(B)):
        B[i] += B[i - 1]
    A = list(set(A))
    (g, s) = (A[0], A[0])
    for i in range(1, len(A)):
        C.append(s + A[i] - gcd(A[i], g))
        if C[-1] != s + A[i] - g:
            for j in range(i + 1, len(A)):
                C[-1] = min(C[-1], s + A[j] - gcd(g, A[j]))
        g = gcd(g, A[i])
        s += A[i]
    ans = 0
    for i in range(K + 1):
        if len(C) > i and len(B) > K - i:
            ans = max(su - B[K - i] - C[i], ans)
    print(ans)

Solution (Python):
import collections
import bisect
import math

def solve():
    (n, m, k) = list(map(int, input().split(' ')))
    a = list(map(int, input().split(' ')))
    a.sort()
    a = [0] + a
    t = []
    p = 1
    for i in range(2, n + 1):
        if a[i] == a[p]:
            t.append(a[p])
        else:
            p += 1
            a[p] = a[i]
    n = p
    s = [0] * (n + 1)
    ans = [0] * (n + 1)
    for i in range(1, n + 1):
        s[i] = s[i - 1] + a[i]
    l = 1
    r = 1
    g = 0
    while l < n:
        g = math.gcd(g, a[l])
        while r < n and math.gcd(a[r], g) == g:
            r += 1
        r -= 1
        for i in range(l + 1, n + 1):
            ans[i - 1] = math.gcd(g, a[i]) - a[i]
        for i in range(n - 2, l - 1, -1):
            ans[i] = max(ans[i], ans[i + 1])
        l = r + 1
        r = l
    ans0 = 0
    for i in range(1, len(t)):
        t[i] += t[i - 1]
    for i in range(max(0, k - n + 1), min(len(t), k) + 1):
        sum = 0
        if i == 0 and len(t) > 0:
            sum = t[-1]
        elif len(t) > 0:
            sum = t[-1] - t[i - 1]
        sum += ans[k - i] + s[n] - s[k - i]
        ans0 = max(ans0, sum)
    print(ans0)
n = int(input())
while n > 0:
    solve()
    n -= 1

Solution (Python):
from math import gcd
for _ in range(int(input())):
    (N, M, K) = map(int, input().split())
    A = list(map(int, input().split()))
    su = sum(A)
    A.sort()
    (B, C) = ([0], [0])
    for i in range(1, N):
        if A[i] == A[i - 1]:
            B.append(A[i])
    for i in range(1, len(B)):
        B[i] += B[i - 1]
    A = list(set(A))
    (g, s) = (A[0], A[0])
    for i in range(1, len(A)):
        C.append(s + A[i] - gcd(A[i], g))
        if C[-1] != s + A[i] - g:
            for j in range(i + 1, len(A)):
                C[-1] = min(C[-1], s + A[j] - gcd(g, A[j]))
        g = gcd(g, A[i])
        s += A[i]
    ans = 0
    for i in range(K + 1):
        if len(C) > i and len(B) > K - i:
            ans = max(su - B[K - i] - C[i], ans)
    print(ans)