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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //List Of Intergers – 920G codeforces | |
| //Código por Sofhia de Souza Gonçalves | |
| #include <bits/stdc++.h> | |
| #define pb push_back | |
| #define N 1000000000000000000 | |
| using namespace std; | |
| typedef long long int ll; | |
| int x, p, k; | |
| ll soma, t; | |
| vector < int > primes; //vector que guarda os fatores primos de p | |
| inline void f(int i, ll mult, int qnt) | |
| { | |
| if(mult > t) return; //se o valor for maior que t, retorno | |
| if(i == primes.size()) | |
| { | |
| if(qnt == 0) return; | |
| if(mult == 1) return; | |
| if(qnt%2) soma += (t/mult); //se o conjunto for par, somo | |
| else soma -= (t/mult); //se for ímpar, subtraio | |
| return; | |
| } | |
| f(i+1, mult, qnt); //não adiciono o fator a minha conta | |
| f(i+1, mult*primes[i], qnt+1); //adiciono o fator a minha conta | |
| } | |
| int main() | |
| { | |
| int n; | |
| scanf("%d", &n); | |
| while(n–) | |
| { | |
| scanf("%d %d %d", &x, &p, &k); | |
| for(ll i = 2 ; i*i <= p ; i++) | |
| { | |
| if(p%i) continue; | |
| while(p%i == 0) p /= i; //enquanto p for divisível por i, divido p por i | |
| primes.pb(i); //adiciono i ao vetor de fatores primos de ṕ | |
| } | |
| if(p != 1) primes.pb(p); //verifico se p nao é um fator primo que falta, se for, adiciono ao vetor | |
| soma = 0; | |
| t = x; | |
| f(0, 1, 0); //calculo soma | |
| ll ante = soma; // quantidade de y onde gcd(y, p) != 1 e y <= x | |
| ll ini = x+1, fim = N, r; | |
| while(ini <= fim) | |
| { | |
| t = (ini+fim)/2; | |
| soma = 0; | |
| f(0, 1, 0); //calculo a quantidade de y onde gcd(y, p) != 1 e y <= t | |
| soma -= ante; //retiro os valores y <= x | |
| soma = (t – x) – soma; // (t-x) é o total de valores no intervalo, tirando os y que tem gcd(y, p) != 1 ficamos com os y tais que gcd(y, p) == 1 | |
| if(soma > k) fim = t-1; //se soma for menor que k, diminuo t | |
| else if(soma < k) ini = t+1; //se for maior, aumento t | |
| else | |
| { | |
| fim = t-1; | |
| r = t; //se for igual, guardo t como minha resposta | |
| } | |
| } | |
| printf("%lld\n", r); | |
| primes.clear(); | |
| } | |
| } |