Cod sursa(job #655237)

Utilizator geniucosOncescu Costin geniucos Data 1 ianuarie 2012 21:03:26
Problema Fractii Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<stdio.h>
using namespace std;
long long nr,n,s,p,i,j,aux,nr1,a[1000002],pr[1000002];
long pow(long long x,long long y)
{
	int i1;
	long long p1=1;
	for(i1=1;i1<=y;i1++)
		p1=1LL*p1*x;
	return p1;
}
int main()
{
freopen("fractii.in","r",stdin);
freopen("fractii.out","w",stdout);
scanf("%d",&n);
a[1]=1;
for(i=1;i<=n;i++)
	if(a[i]==0)
	{
		nr++;
		pr[nr]=i;
		for(j=i*i;j<=n;j=j+i)
			a[j]=1;
	}
s=0;
for(i=2;i<=n;i++)
{
	p=1;
	if(i==100)
		p=1;
	aux=i;
	for(j=1;j<=nr&&pr[j]*pr[j]<=aux;j++)
		if(aux%pr[j]==0)
		{
			nr1=0;
			while(aux%pr[j]==0)
			{
				nr1++;
				aux=aux/pr[j];
			}
			p=1LL*p*pow(pr[j],nr1-1)*(pr[j]-1);
		}
	if(aux!=1)
	{
		j=n+1;
		pr[j]=aux;
		nr1=1;
		p=1LL*p*pow(pr[j],nr1-1)*(pr[j]-1);
	}
	s=s+p;
}
printf("%lld\n",1LL*s*2+1);
return 0;
}