Cod sursa(job #492110)

Utilizator mihaif3feier mihai mihaif3 Data 13 octombrie 2010 14:42:48
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
#include <string.h>
#include <math.h>

int d[50], dp[50], nd;
int c[1000001],p[1000001], n;
long long t;
//--------------------------------
void read()
{
	FILE *f = fopen("fractii.in", "rt");
	fscanf(f, "%d", &n);
	fclose(f);
}
//--------------------------------
void desc_prim(int x)
{
	nd = 0;
	while(x > 1)
	{
		d[nd] = (c[x]!=0? c[x]: x);
		dp[nd] = x/(p[x]!=0? p[x]: 1);
		x /= dp[nd++];
	}
}
//--------------------------------
void solve()
{
	memset(c, 0, n*sizeof(*c));
	for(int i=2; i*i<=n; i++)
		if(c[i] == 0)
			for(int j=i; i*j<=n; j++)
				if(c[i*j] == 0)
				{
					c[i*j] = i;
					p[i*j] = (c[j]==i || i==j? p[j]: j);
				}

	t = 1;
	for(int i=2; i<=n; i++)
	{
		desc_prim(i);
		int k = 1;
		for(int j=0; j<nd; j++)
			k *= (d[j]-1)*(dp[j]/d[j]);
		t += k*2;
	}
}
//--------------------------------
void print()
{
	FILE *f = fopen("fractii.out", "wt");
	fprintf(f, "%I64d ", t);
	fclose(f);
}
//--------------------------------
int main(void)
{
	read();
	solve();
	print();
	return 0;
}