Cod sursa(job #178689)

Utilizator firewizardLucian Dobre firewizard Data 14 aprilie 2008 22:04:16
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <stdio.h>
#include <bitset>
#define sqr 1024

using namespace std;

bitset <sqr>prim;
long i,j,t,q,p[500];
long n,x,r,d[20],k[20],f;
long long sum;

long power(long b,long p){
     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);
    
    //preproc
    //numere prime;
    prim.set();
    prim[1]=0;
    for (i=2;i<=sqr;++i)
        if (prim[i]){
           p[++q]=i;
           t=sqr/i;
           for (j=2;j<=t;j++)
               prim[i*j]=0;
        }
        
    scanf("%ld",&n);
    
    for (i=2;i<=n;++i){
        x=i;
        j=1;
        r=0;
        while (p[j]*p[j]<=x){
              if (x%p[j]==0){
                 r++;
                 d[r]=p[j];
                 k[r]=0;
                 while (x%p[j]==0){
                       x/=p[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;
}