Cod sursa(job #1481234)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 4 septembrie 2015 02:38:39
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <cstdio>

using namespace std;

int vaz[1000100];
int v[1000100];

int main()
{
    freopen("fractii.in","r",stdin);
    freopen("fractii.out","w",stdout);
    long long sol=0,s;
    int n,j,i1=0;
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        if(vaz[i]==0)
        {
            i1++;
            v[i1]=i;
            j=1;
            while(i*j<=n)
            {
               vaz[i*j]=1;
               j++;
            }
        }
    }
    for(int i=2;i<=n;i++)
    {
        s=i;
        j=1;
        while(v[j]<=i)
        {
            if(i%v[j]==0) s=s*(v[j]-1)/v[j];
            j++;
            if(v[j]==0) break;
        }
        sol=sol+s;
    }
    sol=sol*2;
    sol++;
    printf("%lld",sol);
    return 0;
}