Cod sursa(job #744332)

Utilizator cipriancxFMI - gr143 Timofte Ciprian cipriancx Data 8 mai 2012 13:32:30
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<iostream>
#include<cstdio>



using namespace std;

long int n;
long int a[20000001];


long int putere(long int baza, int exponent)
{

    if(exponent==0)return 1;
    exponent--;
    long int aux=baza;
    while(exponent)
    {
        baza=baza*aux;
        exponent--;


    }

    return baza;


}
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)*putere(i,kf-1);}
                      else {

                                a[k]*=(i-1)*putere(i,kf-1);


                            }


                  }

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

cout<<2*sum+1;



return 0;
}