Cod sursa(job #1386)

Utilizator AlxCojocaru Alexandru Alx Data 13 decembrie 2006 15:53:12
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
#include <math.h>
using namespace std;
ifstream f("fractii.in");
ofstream g("fractii.out");
int main()
{
 long n,i,prim[1000010],j,tot[1000010];
 long long s=0;
 f>>n;
 for (i=2;i<=n;i++)
  prim[i]=1;
 tot[1]=1;
 for (i=2;i<=n;i++)
 {
  for (j=2;j<=n/i;j++)
   prim[i*j]=0;
  if (prim[i])
   tot[i]=i-1;
  else
  {
   int ok=1;
   for (j=2;j<i&&ok;j++)
    if (prim[j]&&(i%j==0))
    {
     int aux=i;
     while (aux%j==0&&aux>0)
      aux/=j;
     if (aux==1)
      tot[i]=(j-1)*(i/j);
     tot[i]=tot[i/aux]*tot[aux];
     ok=0;
    }
  }
 }
 for (i=1;i<=n;i++)
  s+=tot[i];
 g<<((2*s)-1)<<"\n";
 return 0;
}