Cod sursa(job #744333)

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



using namespace std;

long long n;
long long a[20000001];


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

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


    }

    return baza;


}
int coef(long long div, long long 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 long 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 long sum=0;
for(i=n; i>=2; i--)sum+=a[i];

cout<<2*sum+1;



return 0;
}