Consider solving this problem if the target permutation is an identity permutation.

Consider the relative ordering of elements in the final answer.

Graph Theory

Topological Sorting

Consider which types of elements can't be swapped, and what that means for the final permutation. If two elements at positions ~(i,j, i < j)~ have ~\gcd(\text{T}[i]~, ~\text{T}[j]) > 1~, their relative ordering will be fixed in the final answer. This is because no matter the order of swaps you conduct, they will never be able to swap past each other. This means that in the final answer, we must have ~\text{T}[i]~ appear before ~\text{T}[j]~. Using this fact, we can begin to construct our solution.

For this subtask, iterate through all possible pairs of elements ~(\text{T}[i], \text{T}[j], i < j)~. If ~\gcd(\text{T}[i], \text{T}[j]) > 1~, draw a directed edge pointing from ~\text{T}[i]~ to ~\text{T}[j]~, indicating that we need to place element ~\text{T}[i]~ before element ~\text{T}[j]~ in our final answer. From here, we can do a greedy topological sort on the graph, prioritizing elements with maximal values first to construct our final answer.

~\mathcal{O}(N^2)~

How can we reduce the number of edges?

Consider the factors of each element.

For the full solution, we need a way to reduce the number of edges in the graph. The key insight is that not all edges are necessary. Consider three indices ~(i < j < k)~, where:

~\gcd(\text{T}[i], \text{T}[j]) > 1~, ~\gcd(\text{T}[j], \text{T}[k]) > 1~, and ~\gcd(\text{T}[i], \text{T}[k]) > 1~.

Using our subtask 1 solution, we would draw edges ~i \to j~, ~j \to k~ and ~i \to k~. However, the final edge, ~i \to k~ can be shown to be redundant in our topological sorting. We can ignore these redundant edges by changing the ideology in which we draw our edges.

Consider iterating through all elements from left to right. For each prime factor ~F~ of ~\text{T}[i]~, store the index ~i~ in a vector ~\text{P}[F]~, where ~\text{P}[K]~ stores all the indices that have ~K~ as a prime factor. Since the ~\gcd~ of any two elements in the same vector will be greater than ~1~, we can add edges between all adjacent elements in these vectors to construct the graph. Finally, proceed with the greedy topological sort on the graph as before, prioritizing maximal values first.

~\mathcal{O}(N \log N)~

Originally, the problem was just the identity permutation as the target. Credits to Maillew for suggesting the current version of this problem.