Cod sursa(job #558699)

Utilizator mraresMardare Rares mrares Data 17 martie 2011 13:35:24
Problema Frac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <math.h>
#define nmax 250

using namespace std;

ifstream fin("frac.in");
ofstream fout("frac.out");

int v[nmax];
long long nr, d;
long long n, p, m;
long long sol;
long long q, i, j;
long long rez;
long answer;
long long st, dr;

void calcul()
{
	float val = sqrt(n);
	d = 2;
	nr = 0;
	while(n > 1)
	{
		if(n % d == 0)
			v[++nr] = d;
		while(n % d == 0)
			n /= d;
		if(d > val && n > 1)
		{
			v[++nr] = n;
			n = 1;
		}
		if(d == 2) d+=1;
		else d+=2;
	}
}

int pinex()
{
	rez = 0;
	for(i = 1; i < (1 << nr); ++ i)
	{
		q = 0;
		p = 1;
		for(j = 0; j < nr; ++ j)
			if(i & (1 << j))
			{
				++ q;
				p = p * v[j+1];
			}
		if(q & 1)
			rez += m/p;
		else rez -= m/p;
	}
	return m-rez;
}

int main()
{
	fin >> n >> p;
	st = 1;
	dr = (long long) 1 << 61;
	calcul();
	while(st <= dr)
	{
		m = (st + dr) / 2;
		if(pinex() >= p)
		{
			dr = m-1;
			answer = (long long) m;
		}
		else
			st = m+1;
	}
	fout << answer << "\n";
	return 0;
}

// WTF NU MERGE
// PROBLEMA DE KKT