Cod sursa(job #575625)

Utilizator SmarandaMaria Pandele Smaranda Data 8 aprilie 2011 16:47:25
Problema Mins Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<stdio.h>
long p[1000001];
long f[1000001][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;
}