2266E.md (2196B)
1 Source: https://codeforces.com/problemset/problem/2266/E 2 3 E. Prime Destruction 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 a [multiset](https://en.wikipedia.org/wiki/Multiset) $a$ consisting of $n$ positive integers. 22 23 You may perform the following operation any number of times (possibly zero): 24 25 * Choose an integer $x \gt 1$ from the multiset and a prime divisor $p$ of $x$. Remove one occurrence of $x$ from the multiset and add $p$ copies of $\frac{x}{p}$. 26 27 You are also given an integer $k$ ($1 \le k \le n$). Let $f(k)$ be the minimum number of operations required, starting from the original multiset, until every integer in the multiset is at most $k$. 28 29 Find $f(k)$. 30 31 Input 32 33 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. 34 35 The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the initial size of the multiset and the given integer, respectively. 36 37 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of the multiset. 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, print a single integer $f(k)$. 44 45 Example 46 47 Input 48 49 ``` 50 6 51 52 1 1 53 54 1 55 56 6 2 57 58 6 6 4 3 2 1 59 60 8 1 61 62 8 6 4 3 2 1 8 6 63 64 12 3 65 66 12 10 9 8 7 6 5 4 3 2 1 12 67 68 10 9 69 70 10 9 8 7 6 5 4 3 2 1 71 72 5 5 73 74 5 4 3 2 1 75 ``` 76 77 Output 78 79 ``` 80 0 81 82 4 83 84 25 85 86 15 87 88 1 89 90 0 91 ``` 92 93 Note 94 95 In the first test case, the only element is already at most $k$, so no operations are needed. 96 97 In the second test case, we can perform the following operations: 98 99 $[\color{red}{6},6,4,3,2,1] \rightarrow [\color{red}{2,2,2},6,4,3,2,1]$, 100 101 $[2,2,2,\color{red}{6},4,3,2,1] \rightarrow [2,2,2,\color{red}{2,2,2},4,3,2,1]$, 102 103 $[2,2,2,2,2,2,\color{red}{4},3,2,1] \rightarrow [2,2,2,2,2,2,\color{red}{2,2},3,2,1]$, 104 105 $[2,2,2,2,2,2,2,2,\color{red}{3},2,1] \rightarrow [2,2,2,2,2,2,2,2,\color{red}{1,1,1},2,1]$. 106 107 Thus, $4$ operations are sufficient. It can be shown that no sequence with strictly fewer operations exists.