Pagini recente » Cod sursa (job #1814964) | Cod sursa (job #353387) | Cod sursa (job #304558) | Cod sursa (job #121083) | Cod sursa (job #379769)
Cod sursa(job #379769)
#include<stdio.h>
#include<vector>
#define N 1000000
using namespace std;
int c,d,p,nr,ind;
int x;
int v[N+2][8];
void read()
{
freopen("mins.in","r",stdin);
freopen("mins.out","w",stdout);
scanf("%d%d",&c,&d);
c--;
d--;
}
void ciur()
{
int i,j;
for(i=2;i<=1<<18;i++)
if(v[i][0]==0)
{
for(j=i;j<=1<<18;j+=i)
{
v[j][++v[j][0]]=i;
}
}
}
void back(int k)
{
if(p>c || p>d)
return;
if(k==1+v[ind][0])
{
if(nr&1)
x-=d/p;
else
x+=d/p;
return;
}
back(k+1);
p=p*v[ind][k];
nr++;
back(k+1);
nr--;
p=p/v[ind][k];
}
void rez()
{
int i;
long long sol=d;
for(i=2;i<=c;i++)
{
x=0;
p=1;
ind=i;
nr=0;
back(1);
sol+=x;
}
printf("%lld\n",sol);
}
int main()
{
read();
ciur();
rez();
return 0;
}