Shohag Loves GCD
Contest: CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 1700
Tags: constructive algorithms, greedy, math, number theory

Shohag has an integer $$$n$$$ and a set $$$S$$$ of $$$m$$$ unique integers. Help him find the lexicographically largest$$$^{\text{∗}}$$$ integer array $$$a_1, a_2, \ldots, a_n$$$ such that $$$a_i \in S$$$ for each $$$1 \le i \le n$$$ and $$$a_{\operatorname{gcd}(i, j)} \neq \operatorname{gcd}(a_i, a_j)$$$$$$^{\text{†}}$$$ is satisfied over all pairs $$$1 \le i \lt j \le n$$$, or state that no such array exists.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le m \le n \le 10^5$$$).

The second line contains $$$m$$$ unique integers in increasing order, representing the elements of the set $$$S$$$ ($$$1 \le x \le n$$$ for each $$$x \in S$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, if there is no solution print $$$-1$$$, otherwise print $$$n$$$ integers — the lexicographically largest integer array that satisfies the conditions.

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

Note:
In the first test case, every element in the array belongs to the given set $$$S = \{3, 4, 6\}$$$, and all pairs of indices of the array satisfy the necessary conditions. In particular, for pair $$$(2, 3)$$$, $$$a_{\operatorname{gcd}(2, 3)} = a_1 = 6$$$ and $$$\operatorname{gcd}(a_2, a_3) = \operatorname{gcd}(4, 4) = 4$$$, so they are not equal. There are other arrays that satisfy the conditions as well but this one is the lexicographically largest among them.

In the third test case, there is no solution possible because we are only allowed to use $$$a = [2, 2]$$$ but for this array, for pair $$$(1, 2)$$$, $$$a_{\operatorname{gcd}(1, 2)} = a_1 = 2$$$ and $$$\operatorname{gcd}(a_1, a_2) = \operatorname{gcd}(2, 2) = 2$$$, so they are equal which is not allowed!

Example input:
3
6 3
3 4 6
1 1
1
2 1
2

Example output:
6 4 4 3 4 3 
1 
-1

Editorial:
THOUGHT: For problems where we need to construct something under some conditions, then a good idea is to first see the nature of the sequences that satisfy the conditions. And to find the properties of such sequences we can try to find some necessary conditions that must have to be met for the sequence to satisfy the conditions.
ACTION: The given condition is that $$$a_{\text{gcd}(i, j)} \neq \text{gcd}(a_i, a_j)$$$ all $$$i < j$$$. As the given operation is gcd on indices and values, it's hard to directly find the properties of the sequence.
But what happens when $$$i$$$ divides $$$j$$$? Then $$$a_{\text{gcd}(i, j)} = a_i$$$. So the condition becomes $$$a_i \neq \text{gcd}(a_i, a_j)$$$ which translates to $$$a_i$$$ can not divide $$$a_j$$$ because otherwise $$$\text{gcd}(a_i, a_j) = a_i$$$.
So we have found a necessary condition: for any pair $$$i < j$$$ where $$$i$$$ divides $$$j$$$, $$$a_i$$$ can not divide $$$a_j$$$.
THOUGHT: Hmm, but is the condition sufficient? One way to check the sufficiency is to find a contradiction.
ACTION: Imagine two indices $$$i$$$ and $$$j$$$ where $$$i$$$ does not divide $$$j$$$ but the condition is violated: $$$a_{\text{gcd}(i, j)} = \text{gcd}(a_i, a_j)$$$.
Then $$$g = \text{gcd}(i, j)$$$ is a divisor of both $$$i$$$ and $$$j$$$ and as $$$a_g$$$ divides both $$$a_i$$$ and $$$a_j$$$, so for pair $$$(g, i)$$$ we have $$$a_{\text{gcd}(g, i)} = a_g$$$ and $$$\text{gcd}(a_g, a_i) = a_g$$$ because $$$a_g$$$ divides $$$a_i$$$. So for this pair the condition is violated!
So if the condition is violated for some pair $$$(i, j)$$$ then it is violated for the pair $$$(g, i)$$$ and $$$(g, j)$$$ as well where $$$g = \text{gcd}(i, j)$$$.
So if there is no pair $$$(i, j)$$$ where $$$i$$$ divides $$$j$$$ and the condition is violated, then all the pairs also satisfy the condition. This proves the sufficiency of the condition.
THOUGHT: So we have found a necessary and sufficient condition. Now we need to construct the lexicographically largest sequence that satisfies the condition.
Solution 1:
Consider a multiple chain $$$i_1 < i_2 < \ldots < i_k$$$. Such that $$$i_1$$$ divides $$$i_2$$$, $$$i_2$$$ divides $$$i_3$$$, ..., $$$i_{k-1}$$$ divides $$$i_k$$$.
Then we know that we have to put distinct values for all the indices in the multiple chain otherwise one number will be divisible by another which will violate the condition.
And as we are aiming for the lexicographically largest sequence, it makes sense to put the values in decreasing order in a multiple chain i.e. $$$a_{i_1} > a_{i_2} > \ldots > a_{i_k}$$$. This way we don't have to care about the divisibility condition, as the numbers are in decreasing order.
Now, we definitely will try to put the largest number possible for each index. So what is the largest number that we can put for the index $$$x$$$?
Consider a directed graph where there is an edge from $$$i$$$ to $$$j$$$ if $$$i$$$ divides $$$j$$$. Then the question is what is the length of the longest path in this graph ending at $$$x$$$.
You can find it using a simple DP on this directed acyclic graph in $$$O(n \log n)$$$ time.
But if you think about it, the answer is actually simple. Let $$$p(x)$$$ the number of prime factors of $$$x$$$ counted with multiplicity. Then the answer is $$$p(x) + 1$$$. For example, if $$$x = 2 \cdot 3^2 \cdot 5$$$, then one of the longest chains ending at $$$x$$$ is $$$1 \rightarrow 2 \rightarrow 2 \cdot 3 \rightarrow 2 \cdot 3^2 \rightarrow 2 \cdot 3^2 \cdot 5$$$ which has length $$$4$$$.
We can precalculate the values $$$p(x)$$$ for all $$$1 \leq x \leq n$$$ in $$$O(n \log n)$$$ time using sieve.
So at index $$$i$$$ we will put the ($$$p(i) + 1$$$)-th largest number from the set $$$S$$$. And the largest value of $$$p(i)$$$ for $$$1 \leq i \leq n$$$ is $$$\lfloor \log_2 n \rfloor$$$ for the chain $$$1 \rightarrow 2 \rightarrow 2^2 \rightarrow \ldots \rightarrow 2^{\lfloor \log_2 n \rfloor}$$$.
So if $$$m < \lfloor \log_2 n \rfloor + 1$$$, then we can't construct the sequence and the answer is $$$-1$$$. Otherwise set $$$a_i = s_{m - p(i)}$$$ for all $$$i$$$.
Also, unless you have noticed already, the actual numbers don't matter!
Time Complexity: $$$O(n \log n)$$$
Solution 2:
As we are trying to construct the lexicographically largest sequence, it's always better to take larger values first. Let $$$s_i$$$ be the $$$i$$$-th smallest number in the set $$$S$$$.
• So, initially set $$$a_1 = s_m$$$. Then we can't use $$$s_m$$$ for any other index as it will violate the condition.
• Then set $$$a_2 = s_{m - 1}$$$ (because we can't use $$$s_m$$$). Then we can't use $$$s_{m - 1}$$$ for any other index $$$j$$$ where $$$j$$$ is divisible by $$$2$$$ as it will violate the condition.
• Then set $$$a_3 = s_{m - 1}$$$ (because we can't use $$$s_{m}$$$). Then we can't use $$$s_{m - 1}$$$ for any other index $$$j$$$ where $$$j$$$ is divisible by $$$3$$$ as it will violate the condition.
• Now set $$$a_4 = s_{m - 2}$$$ (because we can't use $$$s_{m - 1}$$$ or $$$s_m$$$). Then we can't use $$$s_{m - 2}$$$ for any other index $$$j$$$ where $$$j$$$ is divisible by $$$4$$$ as it will violate the condition.
• Then for $$$a_5$$$ we can actually use $$$s_{m-1}$$$ as $$$5$$$ is not divisible by $$$2, 3,$$$ or $$$4$$$ so the only constraint is that $$$a_5 \neq a_1$$$.
• ...
Notice that this is a sieve-like process where we are using the maximum number that we can use for the current index and then we are remembering that in the multiples of the current index, the current number can't be used. We can use sets to simulate the process.
So this process will always construct a valid lexicographically largest sequence. If it is not possible to construct the sequence, then the answer is $$$-1$$$.
Also, if you notice the construction process carefully, the actual numbers don't matter!
Time Complexity: $$$O(n \log^2 n)$$$