Solução por Sofhia Souza
Conhecimentos prévios necessários:
Para resolvermos esse problema, faremos o seguinte:
Calcularemos os fatores primos de $$p$$. Faremos isso percorrendo os valores $$i$$ de 2 até $$\sqrt{p}$$(se percorrermos todos os valores até $$p$$, o código ficará muito lento). Para cada $$i$$, verificaremos se é ou não divisível por $$p$$. Se sim, adicionaremos $$i$$ a lista de valores primos de $$p$$, e dividiremos $$p$$ por $$i$$. É importante ressaltar que pode existir um fator primo de $$p$$ maior que $$\sqrt{p}$$. Basta então verificarmos, depois de olhar todos os valores $$i$$, se $$p$$ é diferente de 1. Se for, é o fator primo que resta, então basta adicioná-lo à lista.
Depois, com esses valores primos, calcularemos a quantidade de valores $$y$$ tais que $$gcd(y, p) != 1$$ e $$y \leq x$$ (para isso, usamos o $$PIE$$), e guardaremos essa quantidade na variável $$ante$$.
Após isso, faremos uma busca binária na resposta: Chutaremos um valor $$t$$, que pode ir até $$10^{18}$$, para ser nossa resposta, e calcularemos, usando o $$PIE$$, a quantidade de valores $$y$$ tais que $$gcd(y, p) != 1$$ e $$y \leq t$$. Guardaremos na variável $$soma$$. Subtrairemos disso a variável $$ante$$, para que $$soma$$ guarde apenas a quantidade de valores $$y$$ tais que $$gcd(y, p) != 1$$ e $$x < y \leq t$$. Assim, fazendo $$soma = (t-x) – soma$$, teremos a quantidade de valores $$y$$ tais que $$gcd(y, p) = 1$$ e $$x < y \leq t$$. Se essa quantidade for igual a $$k$$, $$t$$ é a resposta. Se for menor, aumentamos o $$k$$ na busca, e se for maior, diminuímos o $$k$$ na busca.
Analisando a complexidade: para calcularmos os primos, gastamos $$O(n*\sqrt{p})$$. Para cada calculo da quantidade de gcds, gastamos $$O(2^{8})$$ aproximadamente (pois $$p$$ terá no máximo aproximadamente 8 primos, e como calculamos todas as possibilidades de combinação entre eles, faremos no máximo aproximadamente $$2^8$$ cálculos). Como fazermos esses cálculos para cada caso de teste no máximo $$log(10^{18})$$ vezes (por conta da busca binária), eles tomarão cerca de $$O(log(10^{18})*2^8*n)$$. Assim, a complexidade total do código fica aproximadamente $$O(log(10^{18})*2^8*n)$$. O limite de tempo do problema é de 5 segundos, então o algoritmo consegue rodar dentro do tempo.
Segue o código para melhor entendimento:
https://gist.github.com/sofhiasouza/c8ab6f778f32ae7cd2eacd41a1aba3f6