Cod sursa(job #528055)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 1 februarie 2011 20:45:49
Problema Fractii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<fstream>
#include<math.h>
#include<iostream>
using namespace std;
int f[1000],e[1000];

int RidicareLaPutere(int x,int n)
{
	int p=1;
	while(n>0)
	{
		if (n & 1) // n este impar
		{
			p=p*x;
			n--;
		}
	x=x*x;
	n=n>>1; // sau n = n / 2
	}	
	return p ;
}

int main()
{
	clock_t start,stop;
	start=clock();
	int n,i,x,d,nrf,j;
	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++)
			{
				euler=euler*(f[j]-1)*RidicareLaPutere(f[j],e[j]-1);
			}
			sol+=2*euler;
			//memset(f,0,sizeof(f));
			memset(e,0,sizeof(e));
			nrf=0;
		}
	}
	fout<<sol+1<<"\n";
	fout.close();
	stop=clock();
	cout<<(double)(stop-start)/CLOCKS_PER_SEC<<"\n";
	return 0;
}