Cod sursa(job #341695)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 19 august 2009 12:30:54
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<stdio.h>
#define N 1000100
int n,m,i,j,nv,el[N],fact[N];
long long tm,tn,t,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--;sol=n;sol*=m;nv=1;
	for(;;){tn=n/nv;tm=m/nv;t=tn*tm;if(!t)break;v[nv++]=t;}
	for(i=2;i<nv;i++)
	{
		if(el[i])continue;
		if(fact[i])
		{
			v[i]=(fact[i]&1)?-v[i]:v[i];
			sol+=v[i];
			continue;
		}
		v[i]=-v[i];sol+=v[i];
		for(j=i*i;j<=nv;j+=i)
		{
			if(j%i*i==0)el[j]=1;
			else fact[j]++;
		}
	}
	printf("%lld\n",sol);
}