Cod sursa(job #341742)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 19 august 2009 13:59:56
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<stdio.h>
#define N 1000100
int n,m,i,j,k,ii,np,pr[N],s[N],g[N];
long long v1,v2,v[N],sol;
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("mins.in","r",stdin);
	freopen("mins.out","w",stdout);
	scanf("%d%d",&n,&m);
}
void solve()
{
	n--;m--;
	k=n<m?n:m;
	for(i=1;i<=k;i++){v1=(long long)n/i;v2=(long long)m/i;v[i]=v1*v2;s[i]=1;}
	s[1]=1;
	for(i=2;;i++)
	{
		if(i*i>k)break;
		if(pr[i])continue;
		ii=i*i;
		for(j=ii;j<=k;j+=ii){s[j]=0;g[j]=1;}
		for(j=ii;j<=k;j+=i)pr[j]=1;
	}
	for(i=2;i<=k;i++)
	{
		if(g[i])continue;
		if(!pr[i])
		{
			s[i]=-1;
			for(j=i*i;j<=k;j++)
				if(!g[j])
				{
					s[j]=s[i]*s[i/j];
					g[j]=1;
				}
		}
	}
	for(i=1;i<=k;i++)sol+=v[i]*s[i];
	printf("%lld\n",sol);
}