# D. Shohad Loves GCD↵
↵
## English version:↵
↵
**Link to the problem:** [Codeforces Problem 2039D](https://codeforces.net/problemset/problem/2039/D)↵
↵
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: ↵
↵
$$ [x_m, x_{m-1}, x_{m-1}, x_{m-2}, x_{m-1}, x_{m-2}, x_{m-1}, x_{m-3}, \dotsc] $$↵
↵
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:↵
$$ a_k = x_{m-w(k)} $$↵
↵
### 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)}$:↵
$$ a_{\gcd(j, k)} = x_{m-\sum_{i \in \mathbb{N}} \min(\alpha_i, \beta_i)} $$↵
↵
Since $\gcd(j, k) < k$, it follows that:↵
$$ \sum_{i \in \mathbb{N}} \min(\alpha_i, \beta_i) < \sum_{i \in \mathbb{N}} \alpha_i $$↵
↵
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:↵
$$ a_{\gcd(1, k)} = x_m<\neq \gcd(a_1, a_k) = \gcd(x_m, a_k) $$↵
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)$.↵
↵
2. **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:↵
$$ a_{\gcd(q, k)} = a_q = x_{m-j} \neq \gcd(a_q, a_k) = \gcd(x_{m-j}, a_k) $$↵
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$:↵
$$ w(k) = w\left(\frac{k}{p}\right) + 1 $$↵
↵
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:↵
$$ \max_{1 \leq k \leq n} w(k) > m $$↵
↵
as there will not be enough numbers to allocate.↵
↵
↵
## PT-BR↵
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↵
$$a_k = x_{m-w(k)}$$↵
↵
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)}$:↵
↵
$$a_{gcd(j, k)} = x_{m-\sum_{i \in \mathbb{N}}\min(\alpha_i, \beta_i)}$$↵
↵
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$↵
↵
$$w(k) = w(\frac{k}{p}) + 1$$↵
↵
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↵
↵
$$\max_{1 \leq k \leq n}w(k) > m$$↵
↵
pois não vão haver números o suficiente para desconsiderar.
↵
## English version:↵
↵
**Link to the problem:** [Codeforces Problem 2039D](https://codeforces.net/problemset/problem/2039/D)↵
↵
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: ↵
↵
$$ [x_m, x_{m-1}, x_{m-1}, x_{m-2}, x_{m-1}, x_{m-2}, x_{m-1}, x_{m-3}, \dotsc] $$↵
↵
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:↵
$$ a_k = x_{m-w(k)} $$↵
↵
### 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)}$:↵
$$ a_{\gcd(j, k)} = x_{m-\sum_{i \in \mathbb{N}} \min(\alpha_i, \beta_i)} $$↵
↵
Since $\gcd(j, k) < k$, it follows that:↵
$$ \sum_{i \in \mathbb{N}} \min(\alpha_i, \beta_i) < \sum_{i \in \mathbb{N}} \alpha_i $$↵
↵
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:↵
$$ a_{\gcd(1, k)} = x_m
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)$.↵
↵
2. **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:↵
$$ a_{\gcd(q, k)} = a_q = x_{m-j} \neq \gcd(a_q, a_k) = \gcd(x_{m-j}, a_k) $$↵
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$:↵
$$ w(k) = w\left(\frac{k}{p}\right) + 1 $$↵
↵
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:↵
$$ \max_{1 \leq k \leq n} w(k) > m $$↵
↵
as there will not be enough numbers to allocate.↵
↵
↵
## PT-BR↵
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↵
$$a_k = x_{m-w(k)}$$↵
↵
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)}$:↵
↵
$$a_{gcd(j, k)} = x_{m-\sum_{i \in \mathbb{N}}\min(\alpha_i, \beta_i)}$$↵
↵
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
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$↵
↵
$$w(k) = w(\frac{k}{p}) + 1$$↵
↵
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↵
↵
$$\max_{1 \leq k \leq n}w(k) > m$$↵
↵
pois não vão haver números o suficiente para desconsiderar.
