Cod sursa(job #2830470)

Utilizator raul41917raul rotar raul41917 Data 9 ianuarie 2022 22:36:21
Problema Fractii Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fi("fractii.in");
ofstream fo("fractii.out");
int frec[1000000];
int n;
void Determinare(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(frec[i]==0)
        {
            int j=i+1;
            if(frec[i*i]==0 && i*i<=n)
                frec[i*i]=(i-1)*i;
            while(i*j<=n)
            {
                if(frec[i]==0 && frec[j]==0)
                    frec[i*j]=(i-1)*(j-1);
                else
                {
                    if(j%i==0)
                        frec[i*j]=frec[j]*i;
                    else
                        frec[i*j]=frec[j]*(i-1);
                }
                j++;
            }
        }
    }
}
int main()
{
    fi>>n;
    Determinare(n);
    long long sum=1;
    for(int i=2;i<=n;i++)
    {
        if(frec[i]==0)
            sum+=2*(i-1);
        else
            sum+=2*(frec[i]);
    }
    fo<<sum;
    return 0;
}