Cod sursa(job #126364)

Utilizator AndreyPAndrei Poenaru AndreyP Data 21 ianuarie 2008 22:30:20
Problema Fractii Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<stdio.h>
#include<math.h>
char c[1001];
int b[1001],k[1001],e[1001];
int main()
{
	int i,j,m=0,n,x,a,t;
	unsigned long ft=0,f;
	freopen("fractii.in", "r", stdin);
	freopen("fractii.out", "w", stdout);
	c[0]=c[1]=1;
	for(i=4; i<1001; i+=2)
		c[i]=1;
	for(i=3; i*i<1001; i+=2)
		if(!c[i])
			for(j=i+i+i; j<1001; j+=i+i)
				c[j]=1;
	b[++m]=2;
	for(i=3; i<1001; i+=2)
		if(!c[i])
			b[++m]=i;
	scanf("%d", &n);
	for(i=2; i<=n; i++)
	{
		x=i;
		f=1;
		t=0;
		for(j=1; j<=m; j++)
			e[j]=0;
		for(j=1; (j<=m)&&(x!=1); j++)
		{
			if(x%b[j]==0)
			{
				k[++t]=j;
				while(x%b[j]==0)
				{
					x=x/b[j];
					e[j]++;
				}
			}
		}
		for(j=1; j<=t; j++)
		{
			a=k[j];
			f=f*(b[a]-1)*pow(b[a],e[a]-1);
		}
		if(x!=1)
			f=f*(x-1);
		ft=ft+f;
	}
	ft=ft+ft+1;
	printf("%lu\n", ft);
	return 0;
}