Cod sursa(job #528133)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 2 februarie 2011 09:11:59
Problema Fractii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<fstream>
#include<math.h>
using namespace std;
int f[1000],e[1000];
int main()
{
	int n,i,x,d,nrf,j,p,n1,x2;
	double rad,x1;
	long long euler,sol=0;
	ifstream fin("fractii.in");
	fin>>n;
	fin.close();
	ofstream fout("fractii.out");
	if(n==1) fout<<1<<"\n";
	else
	{
		for(i=2;i<=n;i++)
		{
			nrf=0;
			x=i;
			if(x%2==0)
			{
				f[++nrf]=2;
				while(x%2==0)
				{
					x=x/2;
					e[nrf]++;
				}
			}
			d=3;
			while(x!=1)
			{
				if(x%d==0)
				{
					f[++nrf]=d;
					while(x%d==0)
					{
						x=x/d;
						e[nrf]++;
					}
				}
				else
				{
					x1=x;
					rad=sqrt(x1)+1;
					while(x%d && d<rad)
						d+=2;
					if(d>rad) {f[++nrf]=x; e[nrf]=1; x=1;}
				}
			}
			euler=1;
			for(j=1;j<=nrf;j++)
			{
				p=1;
				n1=e[j]-1;
				x2=f[j];
				while(n1>0)
				{
					if (n1 & 1)
					{
						p=p*x2;
						n1--;
					}
					x2=x2*x2;
					n1=n1>>1;
				}	
				euler=euler*(f[j]-1)*p;
			}
			sol+=2*euler;
			memset(e,0,sizeof(e));
		}
	}
	fout<<sol+1<<"\n";
	fout.close();
	return 0;
}