Cod sursa(job #2373865)

Utilizator Gheorghita_VladGheorghita Vlad Gheorghita_Vlad Data 7 martie 2019 15:33:18
Problema Fractii Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>

using namespace std;
ifstream f("fractii.in");
ofstream g("fractii.out");
int v[1000005],k,n,nr,x,sol;
bool cr[1000005];
void ciur()
{
    int i,j;
    cr[1]==1;
    cr[0]==1;
    for (i=2;i*i<=n;i++)
        if (cr[i]==0) for (j=2;j*i<=n;j++) cr[i*j]=1;
    for (i=2;i<=n;i++) if (cr[i]==0) v[++k]=i;
}
int main()
{
    int i,j;
    f>>n;
    ciur();
    for (i=2;i<=n;i++)
    {
        nr=i;
        x=i;
        j=1;
        while (v[j]*v[j]<=x && x>1)
        {
            if (x%v[j]==0)
            {
                while (x%v[j]==0) x/=v[j];
                nr=nr*(v[j]-1)/v[j];
            }
            j++;
        }
        if (x>1) nr=nr*(x-1)/x;
        sol+=2*nr;
    }
    g<<sol+1;
    return 0;
}