codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.