D. Shohad Loves GCD
Link para problema: https://codeforces.net/problemset/problem/2039/D
Seja $$$S = {x_1, \dotsc, x_m}$$$ o conjunto ordenado em ordem crescente de $$$m$$$ elementos ($$$m \leq n$$$). Denote por $$$a = [a_1, \dotsc, a_n]$$$ o array que queremos montar.
Note que, como queremos maximizar $$$a$$$ na ordem lexicográfica, qualquer solução $$$a'$$$ que fixa um prefixo $$$a[0..i]$$$ e melhora o elemento $$$i+1$$$ imediatamente é melhor, independente do que vem depois. Logo, gulosamente tentaremos colocar os maiores elementos no início. Segue portanto que $$$a_1 = x_m$$$.
Sugestão: realize a solução genérica do problema para $$$n=1,2,3,\dotsc$$$, para um conjunto $$$S = {x_1, \dotsc, x_m}$$$. Você irá observar que a solução segue um padrão: $$$[x_m, x_{m-1}, x_{m-1}, x_{m-2}, x_{m-1}, x_{m-2}, x_{m-1}, x_{m-3}, \dotsc]$$$. Esse padrão de fato pode ser formalizado da seguinte forma:
Teorema 1: se $$$k = \prod_{i \in \mathbb{N}}p_i^{\alpha_i}$$$ é a decomposição de $$$k$$$ em primos, definindo $$$w(k) = \sum_{i \in \mathbb{N}}\alpha_i$$$ então
Procedemos por indução, com o caso base $$$k = 1$$$ trivial, já que $$$a_1 = x_m$$$ sempre. Suponha então como hipótese indutiva que a solução ideal para $$$a[1..k-1]$$$ é construído dessa forma.
Primeiro mostramos que colocar $$$a_k = x_{m-w(k)}$$$ é válido. De fato, para todo $$$1 \leq j < k$$$ com $$$j = \prod_{i \in \mathbb{N}}p_i^{\beta_i}$$$, temos que $$$gcd(j, k) < k$$$ e portanto vale a hipótese indutiva sobre $$$a_{gcd(j, k)}$$$:
Como $$$gcd(j, k) < k$$$ então $$$\sum_{i \in \mathbb{N}}\min(\alpha_i, \beta_i) < \sum_{i \in \mathbb{N}} \alpha_i$$$ e logo, por possuir um índice maior no conjunto $$$S$$$, $$$a_{gcd(j, k)} > a_k \geq gcd(a_j, a_k)$$$, e portanto em especial são diferentes.
Para mostrar que essa escolha de $$$a_k$$$ é máxima, vamos mostrar que seu índice em $$$S$$$ é máximo, o que é suficiente por $$$S$$$ estar ordenado.
- Se $$$k$$$ é primo, então $$$w(k) = 1$$$ e $$$a_k = x_{m-w(k)} = m-1$$$, e isso é evidentemente a melhor solução: analisando o par $$$(1, k)$$$ temos que $$$a_{gcd(1,k)} = x_m < gcd(a_1, a_k) = gcd(x_m, a_k)$$$ de onde segue que $$$a_k \neq x_m$$$, e para todo $$$2 \leq j < k$$$ temos que $$$gcd(2, k) = 1$$$ e logo já segue que $$$a_1 = x_m > a_j \geq gcd(a_j, a_k)$$$.
- Se $$$k$$$ não é primo, defina por $$$w(k) = \sum_{i \in \mathbb{N}}\alpha_i$$$ a quantidade de fatores primos em $$$k$$$ com multiplicidade. Para todo $$$0 \leq j < w(k)$$$, considerando um divisor $$$q | k$$$ com $$$j$$$ fatores primos (considerando multiplicidade), então precisamos que $$$a_{gcd(q, k)} = a_{q} = x_{m-j}$$$ seja diferente de $$$gcd(a_q, a_k) = gcd(x_{m-j}, a_k)$$$ e portanto $$$a_k \neq x_{m-j}$$$ para todo $$$0 \leq j < w(k)$$$, provando a maximalidade de escolher $$$a_k = x_{m-w(k)}$$$.
Isso prova o teorema por indução.
Portanto, temos que $$$a_k = x_{m-w(k)}$$$. Porém note que para todo primo $$$p$$$ que divida $$$k$$$
e podemos simplesmente iterar, para cada $$$k=2..n$$$, pelos $$$O(\sqrt{k})$$$ primeiros números para encontrar o menor fator primo, e resolver em $$$O(n\sqrt{n})$$$, o que já é suficiente para passar, ou utilizar crivo + SPF e resolver em $$$O(n \log \log n)$$$ para passar no tempo limite com folga.
Além disso, já temos nossa condição de impossibilidade: a solução é impossível se e somente se
pois não vão haver números o suficiente para desconsiderar.
