Cod sursa(job #107868)

Utilizator hadesgamesTache Alexandru hadesgames Data 20 noiembrie 2007 18:09:58
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>
#include <math.h>
int p[1000001],m,a[80000],t[1000001];
void  calc(int n) {  
    int i, j;  
    for (i = 2; i <= n; ++i) {  
		if (p[i] == 0) {  
			m++;
			a[m]=i;
			for (j = i + i; j <= n; j += i) {  
				p[j] = 1;  
			}  
		}  
    }  
}  
/*int t(int x)
{
	int i,aux,e,put;
	if (p[x]==0)
		return x-1;
	if (x==1)
		return 1;
	for (i=1;i<=m;i++)
	{
		if (x%a[i]==0)
		{
			aux=x;
			e=0;
			put=1;
			while (aux%a[i]==0)
			{
				aux/=a[i];
				e++;
				put*=x;
			}
			put/=x;
			return (x-1)*put +t(aux);
		}
	}
	return 0;
}*/
int main()
{
	FILE *in,*out;
	int n,i,aux,j;
	double nr,p2,s;
	in=fopen("fractii.in","r");
	out=fopen("fractii.out","w");
	fscanf(in,"%d",&n);
	calc(n);
	nr=n;
	t[1]=1;
	nr=n;
	for (i=2;i<=n;i++)
	{
		if (p[i]==0)
		{
			nr+=n-n/i;
		}
		else
		{
			aux=i;
			s=n;
			for(j=1;j<=m;j++) 
				if (i%a[j]==0)
				{
					while (aux%a[j]==0)
					{
						aux/=a[j];
					}
					p2=(double)n*(double)a[j]/(double)(n-n%a[j]);
					s*=(p2-1)/(p2);
					if (aux==1||aux==0)
						break;
				}
			nr+=s;
			
		}
	}
	fprintf(out,"%lld\n",(long long)floorl(nr));
	fclose(in);
	fclose(out);
	return 0;
	
}