Cod sursa(job #401825)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 23 februarie 2010 09:40:06
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.35 kb
Raporteaza aceasta sursa 
#include<stdio.h>
#define Nmax 1000010
int phi[Nmax],i,j,n;
long long s;

int main()
{
	freopen("fractii.in","r",stdin);
	freopen("fractii.out","w",stdout);
	
	scanf("%d",&n);
	
	for(i=1;i<=n;i++)
		phi[i]=i-1;
	
	for(i=1;i<=n;i++)
	{
		for(j=i+i;j<=n;j+=i)
			phi[j]-=phi[i];
		s+=phi[i];
	}
	
	printf("%lld",2*s+1);
	return 0;
}