Solução Informática Avançado - Semana 73

Solução por Sofhia Souza

Conhecimentos prévios necessários:

• Princípio da Inclusão e Exclusão (PIE)
• Busca Binária

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: