Rayan vs. Rayaneh
Contest: Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
Difficulty rating: 3300
Tags: brute force, dfs and similar, dp, number theory

Rayan makes his final efforts to win Reyhaneh's heart by claiming he is stronger than Rayaneh (i.e., computer in Persian). To test this, Reyhaneh asks Khwarizmi for help. Khwarizmi explains that a set is integer linearly independent if no element in the set can be written as an integer linear combination of the others. Rayan is given a set of integers each time and must identify one of the largest possible integer linearly independent subsets.

Note that a single element is always considered an integer linearly independent subset.

An integer linearly combination of $$$a_1, \ldots, a_k$$$ is any sum of the form $$$c_1 \cdot a_1 + c_2 \cdot a_2 + \ldots + c_k \cdot a_k$$$ where $$$c_1, c_2, \ldots, c_k$$$ are integers (which may be zero, positive, or negative).

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$), the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), the size of the set. The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^6$$$.

Output format:
In the first line of each test case print the size of the largest integer linearly independent subset.

In the next line, print one such subset in any order. If there are multiple valid subsets, print any one of them.

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

Note:
In example 1, $$$\{4, 6\}$$$ is an integer linearly independent subset. It can be proven that there is no integer linearly independent subset with at least $$$3$$$ elements.

In example 2, $$$\{35, 21, 30\}$$$ is an integer linearly independent subset because no integer linear combination of any two elements can create the third. There is no integer linearly independent subset with at least $$$4$$$ elements.

In example 3, $$$\{2, 3, 6\}$$$ is not an integer linearly independent subset since $$$6$$$ can be written as $$$6 \cdot 2 + (-2) \cdot 3$$$, which is an integer linear combination of $$$\{2, 3\}$$$.

Example input:
3
5
2 4 6 8 10
5
12 15 21 30 35
3
2 3 6

Example output:
2
4 6
3
35 21 30
2
2 3

Editorial:
1. According to Bézout's Identity, we can compute $$$\gcd(x_1, \ldots, x_t)$$$ and all its multipliers as an integer linear combination of $$$x_1, x_2, \ldots, x_t$$$.
2. A set $$$\{a_1, \ldots, a_k\}$$$ is good (integer linearly independent) if for every $$$i$$$, $$$\gcd(\{a_j \mid j \neq i\}) \nmid a_i$$$.
3. A set $$$\{a_1, \ldots, a_k\}$$$ is good if and only if there exists a set $$$\{{p_1}^{q_1}, {p_2}^{q_2}, \ldots, {p_k}^{q_k}\}$$$ such that $$${p_i}^{q_i} \mid a_j$$$ for $$$j \neq i$$$ and $$${p_i}^{q_i} \nmid a_i$$$.
4. The set $$$\{a_1, \ldots, a_k\}$$$ can be identified by determining $$$\{{p_1}^{q_1}, {p_2}^{q_2}, \ldots, {p_k}^{q_k}\}$$$. Assume $$$p_1^{q_1} < p_2^{q_2} < \ldots < p_k^{q_k}$$$, where $$$p_i \neq p_j$$$ and $$$p_i$$$ is prime.
5. Let $$$G = {p_1}^{q_1} \cdot {p_2}^{q_2} \ldots \cdot {p_k}^{q_k}$$$. Then $$$\{a_1, \ldots, a_k\}$$$ is good if and only if $$$\frac{G}{{p_i}^{q_i}} \mid a_i$$$ and $$$G \nmid a_i$$$ for every $$$i$$$.
6. The answer is a singleton if, for every pair of numbers $$$x$$$ and $$$y$$$ in the array, $$$x \mid y$$$ or $$$y \mid x$$$. Since the numbers are distinct, a good subset $$$\{a_1, a_2\}$$$ can always be found by searching the first $$$\log M + 2$$$ elements.
7. Define $$$CM[i]$$$ (count multipliers of $$$i$$$) as the number of $$$x$$$ such that $$$i \mid a_x$$$. This can be computed in $$$\mathcal{O}(n + M \log M)$$$.
8. A corresponding set $$$\{a_1, \ldots, a_k\}$$$ exists for a set $$$\{{p_1}^{q_1}, {p_2}^{q_2}, \ldots, {p_k}^{q_k}\}$$$ if and only if $$$CM[\frac{G}{{p_i}^{q_i}}] > CM[G] \geq 0$$$ for all $$$i$$$.
9. Iterate over all valid sets of the form $$$\{{p_1}^{q_1}, {p_2}^{q_2}, \ldots, {p_k}^{q_k}\}$$$, and check if a corresponding $$$\{a_1, a_2, \ldots, a_k\}$$$ exists. Note that $$$k \geq 3$$$ since a good subset $$$\{a_1, a_2\}$$$ is found using another method.
10. We know $$$\frac{G}{{p_1}^{q_1}} \leq M$$$ and also $$${p_1}^{q_1} \leq \sqrt{M}$$$, as $$${p_1}^{q_1} \leq \sqrt{{p_2}^{q_2} \cdot {p_3}^{q_3}} \leq \sqrt{\frac{G}{{p_1}^{q_1}}} \leq \sqrt{M}$$$.
11. There are $$$\sum_{i=1}^{\frac{\log M}{2}} P[\lfloor \sqrt[2i]{M} \rfloor]$$$ numbers in the form $$${p_1}^{q_1}$$$, where $$$P[i]$$$ denotes the number of primes in the range $$$[1, i]$$$. This count is $$$\mathcal{O}(\frac{\sqrt M}{\log M})$$$.
12. The value of $$$k$$$ is at most 6 (denoted as $$$K$$$), as $$${p_2}^{q_2} \ldots {p_k}^{q_k} = \frac{G}{{p_1}^{q_1}} \leq M$$$, and $$$3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \leq M < 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17$$$.
13. We can determine $$$\{a_1, \ldots, a_k\}$$$ from $$$\{{p_1}^{q_1}, {p_2}^{q_2}, \ldots, {p_k}^{q_k}\}$$$ in $$$\mathcal{O}(n \cdot K)$$$.
14. The total time complexity is $$$\mathcal{O}(T \cdot M \cdot \frac{\sqrt M}{\log M} \cdot K + T \cdot M \cdot \log M + \sum_{i=0}^T n_i \cdot K)$$$.