Solução Informática - Nível Avançado - Semana 10

Solução por Leonardo Paes

Não é necessário, mas é interessante dar uma olhada nesse curso antes de ir para a solução:

• Teste de Primalidade, Divisores e Fatoração
• Set
• Map

Seja a fatoração de primos do produtório $x = p_1^{e_1} * p_2^{e_2} * ... * p_k^{e_k}$. O número de divisores de $x$ é $\prod_{i=1}^{k} (e_i + 1)$. Ao utilizarmos análise combinatória, percebemos que podemos escolher qualquer expoente para cada primo $p$ que divide $x$, do expoente $0$ ao expoente máximo de $p$ que divide $x$.

Além disso, $a_i$ só pode ser das seguintes formas: $p*q, p^2, p^3, p^4$, onde $p$ e $q$ são ambos primos. Vamos provar isso por absurdo.

Suponha que $a_i$ tem mais do que $2$ divisores primos distintos. Sejam eles $p, q$ e $r$. Assim, sabemos que: $1, p, q, r, p*q, p*r, q*r$ e $p*q*r$ dividem $a_i$. Como o número de divisores é maior que $5$, a nossa suposição está errada. Portanto, como supomos que $a_i$ tinha mais do que $2$ divisores primos, sabemos que ele tem menos do que $3$. Agora, basta provarmos que o número de divisores de um inteiro da forma $p*q$ está no intervalo de $3$ até $5$. Os seus divisores são: $1, p, q, p*q$. Portanto, são $4$ divisores. Note que se o número for primo, ele terá apenas $2$ divisores.

Por outro lado, há numeros que só tem $1$ divisor primo. Se ele for um quadrado perfeito, ele terá: $1, p$ e $a_i$ como divisores, portanto, $3$. Agora, suponha que $a_i$ seja da forma $p^4$. Seus divisores serão: $1, p, p^2, p^3, p^4$. Note que ele tem $5$ divisores, ou seja, o número limite. Nesse caso, não há como existir $a_i = p^5$.

Agora que provamos as maneiras da fatoração em primos dos números dados, vamos calcular a resposta. Se a forma dele não for $p*q$, é fácil de descobrirmos o primo que o divide. Em c++, podemos utilizar a função $powl(a_i, 1.0/e)$, onde e é o expoente do primo. Note que é mais seguro retirar uma ou duas unidades desse numero e então ir somando +1 até que tal número elevado a $e$ seja igual a $a_i$, já que $powl()$ utiliza numeros decimais. Após descobrirmos se o número possui apenas um divisor primo, utilizaremos um $map<int,int>$ para guardarmos a frequencia desse primo.

Então, resta-nos saber o que fazer com os números $a_i$ da forma $p*q$. A ideia principal é: Suponha que não exista nenhum outro $a_j, j \neq i$. Isso quer dizer que: $gcd(a_i, a_j) = 1$. Para numeros desse tipo, multiplicaremos a resposta por $4$, pois $a_i$ têm primos que nenhum outro $a_j$ possui. Se existir outro número tal que $gcd(a_i, a_j) \neq 1$, há dois casos a considerarmos: Se o $gcd$ deles for igual a eles, eles são o mesmo número, então podemos manter um vetor de frequencias pra cada número, e está resolvido. Caso contrário, manteremos um $set<int,int>$ pra cada $a_i$, guardando divisores primos distintos que formos verificando.

Por fim, basta percorrermos o vetor dado, checando a quantidade de divisores de $a_i$.

• Se for 0, basta multiplicarmos a resposta por $4*frequencia[i]$.
• Se for 1, basta adicionarmos $a_i / s[i].begin()$ em $s[i]$.
• Se for 2, incrementaremos o $map$ referente as frequências dos primos. (Note que no código não há if para esse caso, já que se fosse $1$ virou $2$, e se for 0 não há nada a adicionar).

Para calcularmos a resposta, inicialmente fazemos $resposta = 1$, e então multiplicamos a resposta por quantidade de primos $p$, acrescentando $1$, como explicado previamente.

Código de exemplo: