Cod sursa(job #744302)

Utilizator cipriancxFMI - gr143 Timofte Ciprian cipriancx Data 8 mai 2012 12:25:36
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<iostream>
#include<cstdio>
#include<math.h>


using namespace std;

long int n;
long int a[10000001];



int coef(int div, int nr)
{

int aux=1;

nr=nr/div;
while(nr%div==0)
{ aux++; nr=nr/div;  }

return aux;

}



int main(void)
{

freopen("fractii.in","r",stdin);
freopen("fractii.out","w", stdout);



cin>>n;

long int i,k;


for(i=2; i<=n; i++)
{
if(a[i]==0)  {
                    a[i]=i-1;


                  for(k=2*i; k<=n; k+=i)
                  {
                      int kf=coef(i,k);

                      if(a[k]==0)a[k]=(i-1)*pow(i,kf-1);
                      else a[k]*=(i-1)*pow(i,kf-1);

                  }

                 }
}
long int sum=0;
for(i=2; i<=n; i++)sum+=a[i];

cout<<2*sum+1;
return 0;
}