Subtask 1

First, we can observe that there exists an optimal solution in which every attack involves a subset of exactly ~K~ enemies.

Second, the order of attacks does not matter.

Third, let's consider if we choose ~x = y~, where ~y~ is some composite number. Since ~y~ is composite, then we can write ~y~ as the product of ~a~ and ~b~, where ~a~ and ~b~ are integers greater than ~1~. Then, instead of attacking a subset and choosing ~x = y~, we could instead make two attacks, both using the same subset; the first attack would choose ~x = a~ and the second subset would choose ~x = b~. This would allow us to perform an extra attack than before. Hence, it is optimal to only choose values of ~x~ which are prime.

Since each prime is independent, we can solve the problem separately for each prime, and then add the results together.

Consider any prime. Let us construct an array ~a~, where ~a_i~ represents the number of times that the prime occurs in the prime factorisation of ~h_i~. We will ignore arrays ~a~ with less than ~K~ elements. Then, let us remove zeroes from ~a~ and sort ~a~ in non-increasing order. Then, each operation consists of selecting ~K~ non-zero elements of ~a~ and decrementing all of them.

In this subtask, ~K = 2~. It is well known that the maximum number of operations for this prime is ~\min(\lfloor \frac{\sum_{i=1}^N a_i}{2} \rfloor, \sum_{i=2}^N a_i)~. The left expression bounds the answer because the total sum of ~a~ decreases by ~2~ every operation, and the right expression bounds the answer because at least one of the elements ~a_2, a_3, \dots, a_N~ is decreased in every operation. It can be shown via induction that ~\min(\lfloor \frac{\sum_{i=1}^N a_i}{2} \rfloor, \sum_{i=2}^N a_i)~ operations is achievable (hint: if we choose ~a_1~ and ~a_2~ in our first operation, remove zeroes from ~a~ and sort ~a~ in non-increasing order, then each of the expressions has decreased by at most ~1~). Also, when ~K = 2~, we don't actually need to perform the sort, since we can calculate ~\sum_{i=2}^N a_i~ as ~\sum_{i=1}^N a_i - \max(a_i)~.

For this subtask, we can simply loop through all prime numbers, and then loop through all values of ~h_i~ in order to generate ~a~.

Time complexity: ~\mathcal{O}(N \times \max(h_i))~

Subtask 2

Observe that the total sum of len(~a~) across all primes is equal to the number of distinct prime factors of each element in ~h~. Since ~2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 > 10^6~, each element in ~h~ has at most ~7~ distinct prime factors. Therefore, the total sum of len(~a~) across all primes is at most ~7N~.

Therefore, if we can find the value of ~a~ for each prime quickly, we can solve this subtask efficiently.

It turns out that we can simply modify our sieve of Eratosthenes to find the prime numbers and the value of ~a~ for each prime number at the same time. Our solution then proceeds as in subtask 1.

Time complexity: ~\mathcal{O}(N + \max(h_i) \log(\max(h_i)))~

Subtask 3

The only thing left to handle is how to find the number of operations that can be performed on ~a~ for any ~K~.

One solution is to greedily simulate repeatedly selecting the largest ~K~ elements in ~a~ and decrementing them. Instead of using a priority queue, we should optimise this solution using a frequency array. Details are left as an exercise to the reader.

Alternatively, the number of operations is simply ~\min(\lfloor \frac{\sum_{i=1}^N a_i}{K} \rfloor, \lfloor \frac{\sum_{i=2}^N a_i}{K-1} \rfloor, \lfloor \frac{\sum_{i=3}^N a_i}{K-2} \rfloor, \dots, \sum_{i=K}^N a_i)~. By similar analysis, the ~i~-th of these expressions bounds the answer because out of the elements from the ~i~-th element onwards, at least ~K-i+1~ are decremented every operation. Furthermore, we can again use induction to show that this number of operations is achievable.

Finally, we could binary search for the largest ~z~ such that ~\sum_{i=1}^N \min(z, a_i) \ge z \times K~.

Time complexity: ~\mathcal{O}(N \log(\max(h_i)) + \max(h_i) \log(\max(h_i)))~ or ~\mathcal{O}(N \log N + \max(h_i) \log(\max(h_i)))~ or ~\mathcal{O}(N \log(N \log(\max(h_i))) + \max(h_i) \log(\max(h_i)))~