Pagini recente » Cod sursa (job #1969657) | Cod sursa (job #881066) | Cod sursa (job #1903439) | Cod sursa (job #2602935) | Cod sursa (job #575607)
Cod sursa(job #575607)
#include<stdio.h>
long p[1000051];
long f[1000051][11];
void phi (long n)
{
long i,j;
for (i=1;i<=n;i++)
p[i]=i;
for (i=2;i<=n;i++)
if (p[i]==i)
{
p[i]=i-1;
for (j=i+i;j<=n;j=j+i)
p[j]=p[j]/i*(i-1);
}
}
void prim (long n)
{
long i,j;
f[1][0]=1;
f[1][1]=1;
for (i=2;i<=n;i++)
if (f[i][0]==0)
{
f[i][0]=1;
f[i][1]=i;
for (j=i+i;j<=n;j=j+i)
f[j][++f[j][0]]=i;
}
}
long mins (long x , long y)
{
long i,j,ok=1;
for (i=1;i<=f[x][0] && ok;i++)
for (j=1;j<=f[y][0] && ok;j++)
if (f[x][i]==f[y][j])
ok=0;
return ok;
}
int main()
{
long c,d,minc=-1,mind=-1,num=0,max,i,j,aux;
freopen("mins.in","r",stdin);
freopen("mins.out","w",stdout);
scanf("%ld%ld",&c,&d);
c--;
d--;
if (c<d)
{
aux=c;
c=d;
d=aux;
}
if (c<d)
minc=c;
else
minc=d;
if (c>d)
max=c;
else
max=d;
phi(minc);
num=0;
for (i=2;i<minc;i++)
num=num+p[i]-1;
num=num*2;
num=num+2*minc-1+2*p[minc]-2;
prim(max);
for (i=minc+1;i<=c;i++)
for (j=1;j<=d;j++)
{
if (mins(i,j)==1)
num++;
}
printf("%ld\n",num);
return 0;
}