Preparando MOJI
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.
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$$$.
For each test case, output the maximum possible sum of the array after performing $$$k$$$ operations optimally.
33 8 14 7 85 114 27 2 4 1 63 514 22 3 3
11 14 1
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]$$$.
Informação
Provedor Codeforces
Código CF1806F1
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 10:37:54
Relacionados