Cod sursa(job #178686)

Utilizator firewizardLucian Dobre firewizard Data 14 aprilie 2008 22:03:41
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <stdio.h>
char v[2000002]; 
long long n,i,j,d[1000000],pr[1000000],f,k[1000000],c,nrp,x,r,sum;

long power(long b,long p){//fctie de ridicare la putere
     long rez=1;
     while (p){
           if ((long)(p&1)==1)
              rez*=b;
           b*=b;p>>=1;
     }
return rez;
}

int main()   
{        
freopen("fractii.in","r",stdin);      
freopen("fractii.out","w",stdout);      
     
scanf("%lld",&n);      

                
//-------------ciur
c++;pr[c]=2;   
for(i=3;i*i<=n;i=i+2)      
   if(!v[i]) {pr[++c]=i;           
    for(j=3*i;j*j<=n;j=j+2*i)  v[j]=1;       
   }  
nrp=c;   
//-------------ciur


for (i=2;i<=n;i++)
{
    x=i;
    j=1;r=0;
    while (pr[j]*pr[j]<=i){
          if (i%pr[j]==0){
             r++;
             d[r]=pr[j];
             k[r]=0;
             while (x%pr[j]==0){
                       x/=pr[j];
                       k[r]++;
                 }
              }
              j++;
        }
        if (x!=1){r++;d[r]=x;k[r]=1;}
        f=1;
        for (j=1;j<=r;j++)
            f*=(d[j]-1)*power(d[j],k[j]-1);
        sum=(long long)sum+2*f;
             
}
printf("%lld\n",sum+1);
return 0;  
}