Cod sursa(job #1226488)

Utilizator Johnny07Savu Ioan-Daniel Johnny07 Data 5 septembrie 2014 17:45:46
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("fractii.in");
ofstream g("fractii.out");
long long nrt;
int s[1000005],i,a[800005],aux,n,nr;

void Erathostene (int k)
{
    int i,j;
    for (i=2;i<=k;i++)
        if (s[i]==0) for (j=i+i;j<=k;j+=i) s[j]=1;
}

int solve (int k)
{
    //cout<<i<<" "<<nr<<" ";
    int sus=1,j,jos=1;
    for (j=1;j<=nr;j++)
    {
        if (k%a[j]==0) {sus=sus*(a[j]-1);jos*=a[j];}
    }
    //cout<<"\n";
    sus*=k;
    //cout<<2*sus/jos<<"\n";
    return 2*sus/jos;

}


int main()
{
    f>>n;
Erathostene(n);
a[nr]=1;
nrt=1;
for (i=2;i<=n;i++) {if (s[i]==0) {nr++;a[nr]=i;nrt=nrt+2*(i-1);}
else {aux=solve(i);nrt+=aux;}
}
g<<nrt;



    return 0;
}