Cod sursa(job #198132)

Utilizator alex.cepoiAlexandru Cepoi alex.cepoi Data 8 iulie 2008 19:13:08
Problema Fractii Scor 50
Compilator c Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <stdio.h>

int a[1000000];

long div (long a)
{
	if (a%2==0) return 2;
	int i;
	for (i=3; i<=a/2; i+=2)
		if (a%i==0) return i;
	return 1;
}

int main()
{
	long n, i, j ;
	freopen ("fractii.in", "r", stdin);
	scanf ("%ld", &n);
	fclose(stdin);
	

	a[0]=1;
	
	long long s=1;
	for (i=2; i<=n; ++i)
	{
		long d= div(i);
		if (d!=1)
		{
			long x=1;
			j=i;
			while (j%d==0)
			{
				x*=d;
				j/=d;
			}
			a[i-1]=(x-x/d)*a[j-1];
		}
		else a[i-1]=i-1;
		s+=2*a[i-1];
	}
	
	freopen ("fractii.out", "w", stdout);
	printf ("%lld", s);
	fclose(stdout);
	return 0;
}