# Cod sursa(job #1468727)

Utilizator Data 6 august 2015 20:02:45 Frac 100 cpp done Arhiva de probleme 1.41 kb
``````#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<int> factori;
long long fp[1 << 12];

void factorize(long long n) {
for (long long i = 2; i * i <= n; ++i) {
if (n % i == 0) {
factori.push_back(i);
while (n % i == 0) n /= i;
}
}
if (n != 1) factori.push_back(n);
}

int relprime(long long x) {
for (int i = 0; i < factori.size(); ++i) {
if (x % factori[i] == 0) return false;
}
return true;
}

long long get_ord(long long m) {
long long sol = 0;
for (int i = 1; i < (1 << factori.size()); ++i) {
sol += m / fp[i];
}
return m - sol;
}

int main()
{
ifstream in("frac.in");
long long n, p;
in >> n >> p;
factorize(n);
fp[0] = 1;
for (int i = 0; i < factori.size(); ++i) {
fp[1 << i] = factori[i];
}
for (int i = 1; i < (1 << factori.size()); ++i) {
if ((i & (i - 1)) != 0) {
fp[i] = fp[i & (i - 1)] * fp[i - (i & (i - 1))] * (-1);
}
}
long long li = 1;
long long lf = (1ll << 62);
while (li < lf) {
long long m = (li + lf) / 2;
long long order = get_ord(m);
//std::cerr << "li,lf,m,order: " << li << ", " << lf << ", " << m << ", " << order << std::endl;
if (order < p) {
li = m + 1;
} else if (order > p) {
lf = m - 1;
} else {
li = lf = m;
}
}

while (relprime(li) == false) li--;

ofstream out("frac.out");
out << li << "\n";
out.close();

return 0;
}
``````