Pagini recente » Cod sursa (job #1109168) | Cod sursa (job #2675745) | Cod sursa (job #2781884) | Cod sursa (job #1218643) | Cod sursa (job #476085)
Cod sursa(job #476085)
#include<fstream>
using namespace std;
ifstream in("mins.in");
ofstream out("mins.out");
bool ciur[1<<10];
int nrprm[10000],l;//vector cu nr prime
void primi()
{
for(int i=2;i*i<=(1<<10);i++)
if(!ciur[i])
for(int j=i*i;j<=(1<<10);j+=i)
ciur[j]=true;
ciur[1]=true;
for(int i=2;i<=(1<<10);i++)
if(!ciur[i])
{
nrprm[++l]=i;
}
}
int d[16],k;
void f_primi(int x)
{
int i;
for(i=1;nrprm[i]*nrprm[i]<=x;i++)
{
if(!(x%nrprm[i]))
d[++k]=nrprm[i];
while(x%nrprm[i]==0)
x/=nrprm[i];
}
if(x!=1)
d[++k]=x;
}
bool sol[16];
int prod[1<<15],nr;
void prelucrare()
{
int q=0,sum=1;
for(int i=1;i<=k;i++)
if(sol[i])
{
//out<<i<<" ";
q++;
sum*=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-1)/prod[i];
return s;
}
void reset()
{
k=0;
nr=0;
}
int main()
{
primi();
int x,y;
long long sumaa=0;
in>>x>>y;
for(int i=1;i<x;i++)
{
f_primi(i);
bkt(1);
sumaa+=suma(y);
reset();
}
out<<sumaa;
return 0;
}