# 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↵
$$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 < 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)$.↵
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úmerosnecessárioso suficiente para desconsiderar.
↵
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 < 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)$.↵
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
