Cod sursa(job #130440)

Utilizator AndreyPAndrei Poenaru AndreyP Data 1 februarie 2008 10:49:59
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<stdio.h>
#define N 1000004
char c[N];
int b[90000];
long long ve[N];
int main()
{
	int i,j,k,x,v,t,w;
	freopen("fractii.in","r",stdin);
	freopen("fractii.out","w",stdout);
	unsigned long long f=0,f1;
	c[0]=c[1]=1;
	for(i=4; i<N; i+=2)
		c[i]=1;
	for(i=3; i*i<N; i+=2)
	{
		if(!c[i])
			for(j=i+i+i; j<N; j=j+i+i)
				c[j]=1;
	}
	b[1]=2;
	k=1;
	for(i=3; i<N; i+=2)
	{
		if(!c[i])
			b[++k]=i;
	}
	scanf("%d",&x);
	ve[1]=1;
	if(x>1)
	{
		for(i=2; i<=x; i++)
		{
			if(!c[i])
			{
				f=f+i-1;
				f1=i-1;
			}
			else
			{
				v=0;
				t=1;
				w=i;
				for(j=1; (j<=k)&&(v==0); j++)
				{
					if(w%b[j]==0)
					{	
						v=1;
						while(w%b[j]==0)
						{
							w=w/b[j];
							t=t*b[j];
						}
					}
				}
				if(t==i)
					f1=(b[j-1]-1)*(i/b[j-1]);
				else
					f1=ve[t]*ve[w];
				f=f+f1;
			}
			ve[i]=f1;
		}
		f=2*f+1;
		printf("%llu\n",f);
	}
	else
		printf("1\n");
	return 0;
}