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: