Cod sursa(job #2238782)

Utilizator Carol_LucaCarol Luca Carol_Luca Data 7 septembrie 2018 15:52:22
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
using namespace std;
ifstream in("fractii.in");
ofstream out("fractii.out");
int n,i,j,nr=0,contor,aux;
long long int cnt,add;
bool ok[1000001];
int p[78499],f[78499];
void ciur()
{
    ok[0]=1;
    ok[1]=1;
    for(i=2;i<=n;i++)
    if(ok[i]==0)
    {
        p[++nr]=i;
        for(j=2;j<=(n/i);j++)
        ok[i*j]=1;
    }
}
int main()
{
    in>>n;
    ciur();
    cnt=1;
    for(i=2;i<=n;i++)
    {
        aux=i;
        contor=0;
        for(j=1;j<=nr&&p[j]<=aux&&aux>1;j++)
        if(aux%p[j]==0)
        {
            f[++contor]=j;
            while(aux%p[j]==0)
            aux/=p[j];
        }
        add=i;
        for(j=1;j<=contor;j++)
        add/=p[f[j]];
        for(j=1;j<=contor;j++)
        add*=(p[f[j]]-1);
        cnt+=(add*2);
    }
    out<<cnt;
    return 0;
}