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:
| //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(); | |
| } | |
| } |
