Prime Divisors Selection
Contest: 2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules)
Difficulty rating: 2700
Tags: binary search, greedy, math, number theory

Suppose you have a sequence of $$$k$$$ integers $$$A = [a_1, a_2, \dots , a_k]$$$ where each $$$a_i \geq 2$$$. A sequence of prime integers $$$P = [p_1, p_2, \dots, p_k]$$$ is called suitable for the sequence $$$A$$$ if $$$a_1$$$ is divisible by $$$p_1$$$, $$$a_2$$$ is divisible by $$$p_2$$$ and so on.

A sequence of prime integers $$$P$$$ is called friendly if there are no unique integers in this sequence.

A sequence $$$A$$$ is called ideal, if each sequence $$$P$$$ that is suitable for $$$A$$$ is friendly as well (i. e. there is no sequence $$$P$$$ that is suitable for $$$A$$$, but not friendly). For example, the sequence $$$[2, 4, 16]$$$ is ideal, while the sequence $$$[2, 4, 6]$$$ is not ideal (there exists a sequence $$$P = [2, 2, 3]$$$ which is suitable for $$$A$$$, but not friendly).

You are given $$$n$$$ different integers $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$. You have to choose exactly $$$k$$$ of them in such a way that they form an ideal sequence, or report that it is impossible. Note that no integer can be chosen more than once.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 1000$$$).

The second line contains $$$n$$$ pairwise distinct integers $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$ ($$$2 \leq x_i \leq 10^{18}$$$).

Output format:
If it is impossible to choose exactly $$$k$$$ integers from $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$ in such a way that the chosen integers form an ideal sequence, print $$$0$$$.

Otherwise, print $$$k$$$ pairwise distinct integers — the elements of the chosen ideal sequence. If there are multiple answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
3 3
2 4 6

Example output:
0

Example input:
3 3
2 4 16

Example output:
2 4 16

Editorial:
Let's find for each prime integer $$$p \leq 10^{9}$$$ amount of integers $$$p^{q}$$$ among the given integers. If there are no more than 1 such integers, this prime $$$p$$$ is not interesting for us: if we add one such integer to the answer, we may always select exactly one divisor $$$p$$$ in a suitable sequence so it will not be friendly.
Otherwise let's call such $$$p$$$ important and find a group $$$X_p$$$ (with some size $$$k_i$$$ > 1) — all integers $$$p^q$$$ in the given set. So we have several ($$$t$$$) such groups with sizes $$$k_1$$$, $$$k_2$$$, ... $$$k_t$$$. Now there are some different cases.
Case 1: required size $$$k \leq k_1 + k_2 + \dots + k_t$$$.
If $$$k$$$ is odd and $$$k_i$$$=2 for each $$$i$$$, we have to find some integer $$$y$$$ that has minimum possible different important primes in factorization (and does not have not important primes). If there is no such $$$y$$$, obviously, there is no solution. Now let there is $$$y$$$ that has $$$u$$$ different primes in factorization. If $$$u \leq (k-1)/2$$$ we may take all $$$u$$$ groups necessary for this integer $$$y$$$ and add some other groups $$$X_p$$$ in order to have exactly $$$k$$$ numbers in the result (if $$$u < (k-1)/2$$$).
If $$$k$$$ is even and $$$k_i$$$ = 2 for each $$$i$$$, we may just take any $$$k/2$$$ groups by 2 integers.
If $$$k_j$$$ > 2 for some $$$j$$$ it is easy to check that we may always find the ideal sequence. Let's start to add groups with the maximum sizes while it is possible. Now we have total size $$$k_1 \leq k$$$ and $$$q = k - k_1$$$ 'empty' space. If $$$q \geq 2$$$, we may just add $$$q$$$ integers from the next group. If $$$q = 1$$$, we may remove one integer from the greatest group (because its size is at least 3) and add 2 integers from the next group.
Case 2: $$$k$$$ > $$$k_1$$$ + $$$k_2$$$ + ... + $$$k_t$$$.
First of all let's take all the groups $$$X_p$$$ to the answer. Now each of the remaining integers is either represented as a product of important primes, or not. If it is represented, then we can add it to the answer and the set will remain ideal. Otherwise if we add such number, we can choose any prime divisor from it that is not important and the set will not be ideal. So, we just have to check whether there are enough integers that are represented as a product of important primes and add any $$$k$$$ - $$$k_1$$$ - $$$k_2$$$ - ... - $$$k_t$$$ of them to the answer. If there are not enough such integers, there is no solution.
How to find all important primes? We are interested only in groups $$$X_p = {p^q}$$$ with sizes at least 2. So each such group either has an integer $$$p^2$$$ or an integer $$$p^q$$$ with $$$q \geq 3$$$. To find all the numbers in the first case, we may just check for each given integer whether it is $$$p^2$$$ for some prime $$$p$$$. For the second case we have $$$p \leq 10^6$$$, so we may find all the possible powers for each prime $$$p \leq 10^6$$$.