Cod sursa(job #795892)

Utilizator veleanduAlex Velea veleandu Data 9 octombrie 2012 20:33:47
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <cstdio>
#include <iostream>
using namespace std;
#define maxn 1001000

    int V[maxn],Rez[maxn];
    int n,i,j,l;


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

    for ( i=1; i<=n; i++ )
        Rez[i]=1;
    for ( i=2; i<=n; i++ )
    {
        if ( !V[i] )
        {
            for ( j=i*i; j<=n; j+=i )
                V[j]=1;
            for ( j=i; j<=n; j+=i )
                Rez[j]*=(i-1);
            for ( l=i*i; l<=n; l*=i )
                for ( j=l; j<=n; j+=l )
                    Rez[j]*=i;
        }
    }
    if ( !n )
    {
        printf("0");
        return 0;
    }
    long long rez=0;
    for ( i=1; i<=n; i++ )
        rez+=(long long)Rez[i];
    rez<<=1;
    rez--;
    cout<<rez<<"\n";
    return 0;
}