2104D.md (2883B)
1 Source: https://codeforces.com/problemset/problem/2104/D 2 3 D. Array and GCD 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an integer array $a$ of size $n$. 22 23 You can perform the following operations any number of times (possibly, zero): 24 25 * pay one coin and increase any element of the array by $1$ (you must have at least $1$ coin to perform this operation); 26 * gain one coin and decrease any element of the array by $1$. 27 28 Let's say that an array is ideal if both of the following conditions hold: 29 30 * each element of the array is at least $2$; 31 * for each pair of indices $i$ and $j$ ($1 \le i, j \le n$; $i \ne j$) the greatest common divisor (GCD) of $a_i$ and $a_j$ is equal to $1$. If the array has less than $2$ elements, this condition is automatically satisfied. 32 33 Let's say that an array is beautiful if it can be transformed into an ideal array using the aforementioned operations, provided that you initially have no coins. If the array is already ideal, then it is also beautiful. 34 35 The given array is not necessarily beautiful or ideal. You can remove any elements from it (including removing the entire array or not removing anything at all). Your task is to calculate the minimum number of elements you have to remove (possibly, zero) from the array $a$ to make it beautiful. 36 37 Input 38 39 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 40 41 The first line of each test case contains a single integer $n$ ($1 \le n \le 4 \cdot 10^5$). 42 43 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 10^9$). 44 45 Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $4 \cdot 10^5$. 46 47 Output 48 49 For each test case, print a single integer — the minimum number of elements you have to remove (possibly, zero) from the array $a$ to make it beautiful. 50 51 Example 52 53 Input 54 55 ``` 56 5 57 58 3 59 60 5 5 5 61 62 4 63 64 2 3 2 4 65 66 1 67 68 3 69 70 3 71 72 2 100 2 73 74 5 75 76 2 4 2 11 2 77 ``` 78 79 Output 80 81 ``` 82 0 83 2 84 0 85 0 86 1 87 ``` 88 89 Note 90 91 In the first example, you don't need to delete any elements, because the array is already beautiful. It can be transformed into an ideal array as follows: $[5, 5, 5] \rightarrow [4, 5, 5] \rightarrow [4, 4, 5] \rightarrow [4, 3, 5]$ (you end up with $3$ coins). 92 93 In the second example, you need to remove $2$ elements so that the array becomes beautiful. If you leave the elements $[2, 3]$ and delete the other elements, then the given array is already ideal (and therefore, beautiful). 94 95 In the third example, you don't need to delete any elements because the array is already ideal (and thus, beautiful). 96 97 In the fourth example, the array is beautiful. It can be transformed into an ideal array as follows: $[2, 100, 2] \rightarrow [2, 99, 2] \rightarrow [2, 99, 3] \rightarrow [2, 98, 3] \rightarrow [2, 97, 3]$ (you end up with $2$ coins).