GCD Master (hard version)
Contest: Codeforces Round 858 (Div. 2)
Difficulty rating: 2900
Tags: greedy, 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 format:
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 format:
For each test case, output the maximum possible sum of the array after performing $$$k$$$ operations optimally.

Constraints:
Time limit: 3.0 s
Memory limit: 1024.0 MB

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]$$$.

Example input:
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

Example output:
11
14
1
18000000000000000000

Editorial:
Hint 1: There is a easy strategy for dealing with repeated elements. Suppose that all elements in $$$a$$$ are pairwise distinct in the following hints.
Hint 2: We will always perform an operation on the minimum element.
Hint 3: The best way is to choose $$$k+1$$$ elements, delete them, and add the gcd of them to the sequence.
Hint 4: After sorting the sequence, you may guess that choosing a prefix is optimal. But actually it is wrong. Try fixing the strategy!
Solution for F1:
First, suppose that all elements in $$$a$$$ are pairwise distinct.
The problem can be rewritten as: Divide the sequence into $$$n-k$$$ groups to maximize the sum of the gcd of each group. Let $$$S_i$$$ represent the elements of a group.
Lemma $$$1$$$: When $$$k>0$$$, the group which the minimum element of the original sequence belongs to satisfies $$$|S_a|>1$$$.
Proof:
If $$$|S_a|=1$$$, we can find a group $$$S_x$$$ such that $$$|S_x|>1$$$. Then replacing the maximum element of $$$S_x$$$ with the minimum element of the original sequence makes the answer greater.
Let $$$a$$$ be the minimum of the sequence and $$$b$$$ be the maximum of $$$S_x$$$.
• the original answer is $$$a+\gcd(S_x)$$$.
• replacing the maximum element of $$$S_x$$$ with the minimum element, the answer is $$$b+\gcd(S_x \setminus \{b\}\cup\{a\}) >b$$$.
$$$\gcd(S_x) \le \max{S_x} - \min S_x = b-\min S_x < b-a$$$, so $$$a+\gcd(S_x)< a+b-a=b<b+\gcd(S_x \setminus \{b\}\cup\{a\})$$$. Q.E.D.
Tips: When $$$\max S_x = \min S_x$$$, $$$\gcd(S_x) \not\le \max{S_x} - \min S_x$$$. That's why all elements in $$$a$$$ need to be pairwise distinct.
Lemma $$$2$$$: When $$$k>0$$$, there's only one $$$S_x$$$ such that $$$|S_x| >1$$$ 。
Proof:
Let $$$S_a$$$ be the group with the minimum element.
Referring to Lemma $$$1$$$, we know $$$|S_a| >1$$$. Then we remove all the elements of $$$S_a$$$ from the sequence, add $$$\gcd({S_a})$$$ to the sequence and subtract $$$|S_a| - 1$$$ from $$$k$$$. It's obvious that $$$\gcd(S_a)$$$ is the minimum element of the newly formed sequence. We can continue the process until $$$k=0$$$, which tells us that only $$$|S_a|=k+1>1$$$. Q.E.D.
We can enumerate $$$\gcd(S_a)$$$ to solve it in $$$O(n+m\ln m)$$$ so far.
How about repeated elements?
We can find that for those repeated elements, the best strategy is to merge them with the same element. In other word, a repeated element $$$x$$$ only decreases the answer by $$$x$$$. So it's independent of the previous part. We just need to enumerate the number of operations we perform for repeated elements.
Solution for F2:
Still suppose that all elements in $$$a$$$ are pairwise distinct.
Suppose $$$a$$$ is sorted.
Lemma $$$3$$$: When $$$k>0$$$, we will choose the first $$$k$$$ elements, and an element from the remaining elements.
That is, $$$S=\{a_1,a_2,\ldots,a_k,a_x\}$$$, where $$$k < x \le n$$$, is the only group with more than one element.
Proof:
Suppose $$$T=\{a_1,a_2,\ldots, a_{p}, a_{c_1}, a_{c_2}, \ldots, a_{c_t}\}$$$, where $$$p+1<c_1<c_2<\cdots<c_t$$$, $$$t\ge 2$$$ and $$$p+t=k+1$$$. Then we can prove that $$$T'=\{a_1,a_2,\ldots, a_{p},a_{p+1}, a_{c_1}, a_{c_2}, \ldots, a_{c_{t-1}}\}$$$ is always a better choice.
Let $$$g=\gcd(T)$$$ and $$$g'=\gcd(T')$$$. We have $$$a_{c_t}-a_{p+1}> a_{c_t}-a_{c_{t-1}}\ge g$$$.
$$$\Delta=ans(T')-ans(T)=a_{c_t}-a_{p+1}+g'-g> g'>0$$$.
So repeating the process, finally we will know that $$$S=\{a_1,a_2,\ldots,a_k,a_x\}$$$, where $$$k < x \le n$$$. Q.E.D.
When there're repeated elements, we need to calculate the answer for $$$k$$$ prefixes. Note that there're only $$$O(\log m)$$$ different prefix gcd. So we can do it in $$$O(n \log^2 m)$$$ (another $$$O(\log m)$$$ comes from calculating gcd). Let $$$g_i$$$ be the prefix gcd. When finding the best pair, we calculate $$$\gcd(g_i,a_j)$$$, which leads to $$$O(n \log^2 m)$$$. $$$g_i\mid g_{i-1}$$$, so $$$\gcd(g_i,a_j)=\gcd(g_i,\gcd(g_{i-1},a_j))$$$. The gcd is non-increasing so the total complexity is $$$O(n \log m)$$$.