Cod sursa(job #84410)

Utilizator ZuziFilip Sanziana Zuzi Data 14 septembrie 2007 22:24:20
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>
#include<math.h>

#define MAX 1000001
#define NMAX 1000000
int  t[1000002];
int  p[78500], num = 1;
long n, nr;
char a[125000];
long long fr = 1;

void ciur()
{
	int i, j;
	for ( i = 4; i <= NMAX; i = i+2)
		a[i>>3] |= ( 1<<(i&7) );
	for ( i = 3; i <= NMAX; i = i+2)
	{
		if ( !(a[i>>3] & ( 1<<(i&7) ) ) )
			for ( j = 2; j*i <= NMAX; j++)
				a[ ( i*j ) >> 3] |= ( 1<<( ( i*j ) & 7 ));
	}
	p[1] = 2;
	for ( i = 3; i <= NMAX; i = i+2 )
		if ( !( a[i>>3] & ( 1<< (i&7) )))
			p[++num] = i;
}

int main()
{
	long i, ci, j;
	int ex;
    long long nr;
	freopen("fractii.in", "r", stdin);
	freopen("fractii.out", "w", stdout);
	scanf("%ld", &n);
	ciur();
	for (i = 1; i <= num; i++)
	{
		nr = p[i];
		for (j = 1; nr <= MAX; j++)
		{
			t[nr] = (p[i] - 1) * (nr / p[i]);
			nr *= p[i];
		}
	}


	for ( i = 2; i <= n; i++)
		if ( t[i] ==0)
		{
			ex = 1;
			ci = i;
			nr = 1;
			for ( j = 1; ex; j++)
				if ( ci % p[j] == 0)
				{
					ex = 0;
					while (ci % p[j] == 0)
						nr *= p[j], ci /= p[j];
				}
			t[i] = t[nr] * t[i/nr];
		}
	for ( i = 2; i <= n; i++)
		fr += 2 * t[i];

	printf("%lld", fr);
	return 0;
}