D. Shohad Loves GCD

English version:

Link to the problem: Codeforces Problem 2039D

Let $$$S = {x_1, \dotsc, x_m}$$$ be the set of $$$m$$$ elements ($$$m \leq n$$$), ordered in increasing order. Denote $$$a = [a_1, \dotsc, a_n]$$$ as the array we want to construct.

Notice that to maximize $$$a$$$ lexicographically, any solution $$$a'$$$ that fixes a prefix $$$a[0..i]$$$ and immediately improves element $$$i+1$$$ is better, regardless of what comes afterward. Thus, we greedily try to place the largest elements at the beginning. It follows that $$$a_1 = x_m$$$.

Suggestion

Solve the problem generically for $$$n = 1, 2, 3, \dotsc$$$ for a set $$$S = {x_1, \dotsc, x_m}$$$. You will observe that the solution follows a pattern:

This pattern can indeed be formalized as follows:

Theorem 1

If $$$k = \prod_{i \in \mathbb{N}}p_i^{\alpha_i}$$$ is the prime factorization of $$$k$$$, then defining $$$w(k) = \sum_{i \in \mathbb{N}}\alpha_i$$$, we have:

Proof

We proceed by induction:

• Base case: $$$k = 1$$$ is trivial since $$$a_1 = x_m$$$ always.
• Inductive step: Assume as the inductive hypothesis that the optimal solution for $$$a[1..k-1]$$$ is constructed this way.

Validity of $$$a_k = x_{m-w(k)}$$$

For any $$$1 \leq j < k$$$ with $$$j = \prod_{i \in \mathbb{N}}p_i^{\beta_i}$$$, we have $$$\gcd(j, k) < k$$$, and hence the inductive hypothesis applies to $$$a_{\gcd(j, k)}$$$:

Since $$$\gcd(j, k) < k$$$, it follows that:

Thus, $$$a_{\gcd(j, k)} > a_k \geq \gcd(a_j, a_k)$$$, and in particular, they are distinct.

Maximality of $$$a_k = x_{m-w(k)}$$$

To show this choice is maximal, we need to show its index in $$$S$$$ is the largest possible, which suffices since $$$S$$$ is ordered.

1. If $$$k$$$ is prime: $$$w(k) = 1$$$, so $$$a_k = x_{m-1}$$$. This is evidently the best solution. Considering the pair $$$(1, k)$$$, we have:

Hence, $$$a_k \neq x_m$$$. For all $$$2 \leq j < k$$$, $$$\gcd(j, k) = 1$$$ because of the primality of $$$k$$$, so $$$a_1 = x_m > a_j \geq \gcd(a_j, a_k)$$$.

1. If $$$k$$$ is not prime: Define $$$w(k) = \sum_{i \in \mathbb{N}}\alpha_i$$$, the total count of prime factors of $$$k$$$ (with multiplicity). For any $$$0 \leq j < w(k)$$$, consider a divisor $$$q \mid k$$$ with $$$j$$$ prime factors. Then:

Therefore, $$$a_k \neq x_{m-j}$$$ for all $$$0 \leq j < w(k)$$$, proving maximality.

This proves the theorem by induction.

Complexity and Implementation

Thus, we have $$$a_k = x_{m-w(k)}$$$. Note that for any prime $$$p$$$ dividing $$$k$$$:

We can iterate, for each $$$k = 2..n$$$, over the $$$O(\sqrt{k})$$$ smallest numbers to find the smallest prime factor, achieving $$$O(n\sqrt{n})$$$ complexity, which suffices to pass. Alternatively, using a sieve with SPF (smallest prime factor), we can solve this in $$$O(n \log \log n)$$$, which easily fits within the time limit.

Impossibility Condition

The solution is impossible if and only if:

as there will not be enough numbers to allocate.

PT-BR

Link para problema: https://mirror.codeforces.com/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.

1. 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 \neq 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(j, k) = 1$$$ e logo já segue que $$$a_1 = x_m > a_j \geq gcd(a_j, a_k)$$$.
2. 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.