GCD Master (easy version) (Codeforces 1806F1)
Tags: Math, number theory

This is the easy 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 10^6$$$; $$$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$$$ and the sum of $$$m$$$ 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:
3
3 8 1
4 7 8
5 114 2
7 2 4 1 6
3 514 2
2 3 3

Sample Outputs:
11
14
1

Solution (Python):
t = int(input())
for _ in range(t):
    (n, m, k) = map(int, input().split())
    a = list(map(int, input().split()))
    cnt = [0] * (m + 1)
    for x in a:
        cnt[x] += 1
    tot = sum(a)
    DP = [0] * (n + 1)
    for gc in range(1, m + 1):
        remsum = tot + gc
        used = 0
        for x in range(gc, m + 1, gc):
            if cnt[x] == 0:
                continue
            used += 1
            remsum -= x
            DP[used] = max(DP[used], remsum)
    ans = DP[k + 1]
    (ctx, base) = (0, 0)
    for x in range(1, m + 1):
        for rep in range(cnt[x] - 1):
            ctx += 1
            base += x
            if ctx <= k + 1:
                ans = max(ans, DP[k + 1 - ctx] - base)
    print(ans)

Solution (Python):
t = int(input())
for _ in range(t):
    (n, m, k) = map(int, input().split())
    a = list(map(int, input().split()))
    cnt = [0] * (m + 1)
    for x in a:
        cnt[x] += 1
    tot = sum(a)
    DP = [0] * (n + 1)
    for gc in range(1, m + 1):
        remsum = tot + gc
        used = 0
        for x in range(gc, m + 1, gc):
            if cnt[x] == 0:
                continue
            used += 1
            remsum -= x
            DP[used] = max(DP[used], remsum)
    ans = DP[k + 1]
    (ctx, base) = (0, 0)
    for x in range(1, m + 1):
        for rep in range(cnt[x] - 1):
            ctx += 1
            base += x
            if ctx <= k + 1:
                ans = max(ans, DP[k + 1 - ctx] - base)
    print(ans)

Solution (Python):
t = int(input())
for _ in range(t):
    (n, m, k) = map(int, input().split())
    a = list(map(int, input().split()))
    cnt = [0] * (m + 1)
    for x in a:
        cnt[x] += 1
    tot = sum(a)
    DP = [0] * (n + 1)
    for gc in range(1, m + 1):
        remsum = tot + gc
        used = 0
        for x in range(gc, m + 1, gc):
            if cnt[x] == 0:
                continue
            used += 1
            remsum -= x
            DP[used] = max(DP[used], remsum)
    ans = DP[k + 1]
    (ctx, base) = (0, 0)
    for x in range(1, m + 1):
        for rep in range(cnt[x] - 1):
            ctx += 1
            base += x
            if ctx <= k + 1:
                ans = max(ans, DP[k + 1 - ctx] - base)
    print(ans)