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:

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: