Pagini recente » Borderou de evaluare (job #1464478) | Cod sursa (job #2475775) | Borderou de evaluare (job #2290532) | Borderou de evaluare (job #490867) | Cod sursa (job #474385)
Cod sursa(job #474385)
#include<fstream>
using namespace std;
ifstream in("frac.in");
ofstream out("frac.out");
long long n,p;
void read()
{
in>>n>>p;
}
int d[16],k;
void f_primi(long long x)
{
long long i;
for(i=2;i*i<=x;i++)
{
if(x%i)
continue;
d[++k]=i;
while(x%i==0)
{
x/=i;
}
}
if(x!=1)
d[++k]=x;
}
bool sol[16];
long long prod[1<<15],nr;
void prelucrare()
{
long long q=0,sum=1;
for(int i=1;i<=k;i++)
if(sol[i])
{
//out<<i<<" ";
q++;
sum*=(long long)d[i];
}
if(q%2)
sum*=-1;
prod[++nr]=sum;
//out<<"prod="<<prod[nr]<<"\n";
}
void bkt(int p)
{
if(p>k)
{
prelucrare();
return;
}
sol[p]=0;
bkt(p+1);
sol[p]=1;
bkt(p+1);
}
long long suma(long long x)
{
long long s=0;
for(int i=1;i<=nr;i++)
s+=x/prod[i];
return s;
}
long long caut(long long x)
{
long long i,pas=(long long)(1)<<61;
for(i=0;pas!=0;pas>>=1)
if(suma(i+pas)<x)
i+=pas;
return i+1;
}
int main()
{
read();
f_primi(n);
bkt(1);
out<<caut(p);
return 0;
}