Cod sursa(job #42925)

Utilizator cc_plusplusMarinescu Alexandru cc_plusplus Data 29 martie 2007 17:11:21
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream.h>
int p[1005], q[1005], dim;
void desc(int n)
{
int i;
dim=0;
if(n%2==0)
  {
  dim++;
  p[dim]=2;
  q[dim]=0;
  while(n%2==0)
       {
       q[dim]++;
       n=n/2;
       }
  }
if(n%3==0)
  {
  dim++;
  p[dim]=3;
  q[dim]=0;
  while(n%3==0)
       {
       q[dim]++;
       n=n/3;
       }
  }
for(i=4;i*i<=n;i=i+3)
   {
   if(n%i==0)
     {
     dim++;
     p[dim]=i;
     q[dim]=0;
     while(n%i==0)
	  {
	  q[dim]++;
	  n=n/i;
	  }
     }
   }
for(i=5;i*i<=n;i=i+3)
   {
   if(n%i==0)
     {
     dim++;
     p[dim]=i;
     q[dim]=0;
     while(n%i==0)
	  {
	  q[dim]++;
	  n=n/i;
	  }
     }
   }
if(n!=1)
  {
  dim++;
  p[dim]=n;
  q[dim]=1;
  }
}
unsigned long long putere(int b, int p)
{
int i;
unsigned long long ret;
ret=1;
for(i=1;i<=p;i++)
   {
   ret=ret*b;
   }
return ret;
}
unsigned long long calc(void)
{
int i;
unsigned long long ret;
ret=1;
for(i=1;i<=dim;i++)
   {
   ret=ret*putere(p[i], q[i]-1)*(p[i]-1);
   }
return ret;
}
int main (void)
{
int i, n;
unsigned long long ret;
ifstream fin("fractii.in");
fin>>n;
fin.close();
ret=0;
for(i=1;i<=n;i++)
   {
   desc(i);
   ret=ret+calc();
   }
ofstream fout("fractii.out");
fout<<(2*ret-1)<<"\n";
fout.close();
return 0;
}