Cod sursa(job #753876)

Utilizator geniucosOncescu Costin geniucos Data 30 mai 2012 18:12:20
Problema Mins Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include<cstdio>
using namespace std;
int c,d,j,i,sf,v[1000007];
long long s;
int min(int a,int b)
{
	if(a<b) return a;
	return b;
}
int main()
{
freopen("mins.in","r",stdin);
freopen("mins.out","w",stdout);
scanf("%d",&c);
scanf("%d",&d);
sf=min(c,d)-1;
c--;
d--;
s=(long long)c*d;
for(i=2;i<=sf;i++)
{
	if(v[i]==0)
	{
		for(j=i;j<=sf;j=j+i)
			v[j]++;
		if(i*i<=sf)
		{
			for(j=i*i;j<=sf;j=j+i*i)
				v[j]=-1;
		}
	}
	if(v[i]>=0)
	{
		if(v[i]%2==1) s=s-(long long)(c/i)*(d/i);
		else s=s+(long long)(c/i)*(d/i);
	}
}
printf("%lld\n",s);
return 0;
}