2156C.md (3823B)
1 Source: https://codeforces.com/problemset/problem/2156/C 2 3 C. Maximum GCD on Whiteboard 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an integer $k$ and $n$ positive integers $a_1, a_2, \ldots, a_n$ written on a whiteboard, where $1\le a_i\le \boldsymbol{n}$. You may perform the following operations: 22 23 * Erase: Choose an integer from the whiteboard and erase it. This operation can be performed at most $k$ times. 24 * Split: Choose an integer $x\ge 3$ from the whiteboard. Split it into three positive integers $x_1$, $x_2$, and $x_3$ such that $x_1 + x_2 + x_3 = x$, and $1\le x_1\le x_2\le x_3$. Then, erase $x$ from the whiteboard and write two new integers $x_1$ and $x_3$ on the whiteboard. Note that $x_2$ is discarded and not written on the whiteboard. This operation may be performed any number of times. 25 26 The beauty of a collection of integers $b$ is defined as the greatest common divisor of all the elements in $b$. Formally, it is the largest integer $d$ such that $d$ divides $x$ for every $x$ that is an element of $b$. 27 28 Your task is to determine the maximum possible beauty of the integers on the whiteboard after performing at most $k$ Erase operations and any number of Split operations. 29 30 Input 31 32 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 33 34 The first line of each test case contains two integers $n$ and $k$ ($1\le n \le 2 \cdot 10^5$, $0 \le k \le n - 1$) — the number of integers on the whiteboard, and the maximum number of Erase operations allowed. 35 36 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le \boldsymbol{n}$) — the integers initially written on the whiteboard. 37 38 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 39 40 Output 41 42 For each test case, output a single integer representing the maximum beauty of the elements written on the whiteboard after performing the operations. 43 44 Example 45 46 Input 47 48 ``` 49 6 50 51 9 1 52 53 4 9 6 8 2 6 7 8 2 54 55 10 1 56 57 4 9 6 8 2 6 7 8 2 7 58 59 7 5 60 61 1 1 2 3 4 5 5 62 63 7 4 64 65 1 1 2 3 4 5 5 66 67 14 3 68 69 14 12 7 12 9 9 12 4 3 1 3 6 9 13 70 71 1 0 72 73 1 74 ``` 75 76 Output 77 78 ``` 79 2 80 81 1 82 83 5 84 85 1 86 87 3 88 89 1 90 ``` 91 92 Note 93 94 In the first test case, you may perform the following sequence of operations: 95 96 * Erase $7$. The whiteboard now contains the integers $[4,9,6,8,2,6,8,2]$. 97 * Split $9$ into three integers $2$, $3$, and $4$. $9$ is erased from the whiteboard, and two new integers $2$ and $4$ are written. The whiteboard now contains the integers $[4,\underline{2,4},6,8,2,6,8,2]$. 98 * Split $8$ into three integers $2$, $2$, and $4$. $8$ is erased from the whiteboard, and two new integers $2$ and $4$ are written. The whiteboard now contains the integers $[4,2,4,6,\underline{2,4},2,6,8,2]$ (It does not matter which $8$ Split is performed on as the ordering in the array does not matter). 99 100 The beauty of the integers on the whiteboard after the operations is $2$ as it is the largest number that divides all the integers on the whiteboard ($2$, $4$, $6$, and $8$). Note that the last operation is unnecessary — the beauty of the integers on the whiteboard after the second operation is already $2$. 101 102 In the second test case, note that the Erase operation can only remove one occurrence of an integer, even if duplicates exist. Here, we are only able to erase one copy of $7$, so there will still be one remaining $7$ on the whiteboard. Hence, we are unable to perform the same sequence of operations as in the first test case. 103 104 In the third test case, we can erase integers $1$, $1$, $2$, $3$, and $4$, leaving only $[5, 5]$ on the whiteboard. Since both numbers are $5$, their greatest common divisor is $5$, and the maximum beauty is $5$.