s73_avançado.cpp

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