Cod sursa(job #1597975)

Utilizator trutruvasilicaHuhurez Marius trutruvasilica Data 12 februarie 2016 15:25:20
Problema Fractii Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <bitset>
using namespace std;
const int N=1000001;
ifstream fin("fractii.in");
ofstream fout("fractii.out");
bool v[N];
int p[N/3];
void ciur(int n)
{
    int i,j;
    for(i=3;i*i<=n;i+=2)
    {
        if(!v[i]) for(j=i+i;j<=n;j+=i) v[j]=1;
    }
    p[++p[0]]=2;
    for(i=3;i<=n;i+=2)
    {
        if(v[i]==0) p[++p[0]]=i;
    }
}
long long desc(int x)
{
    long long sol=1;
    for(int i=1;p[i]*p[i]<=x;i++)
    {
        if(x%p[i]==0)
        {
            int step=1;
            while(x%p[i]==0)
            {
                step=step*p[i];
                x/=p[i];
            }
            step=step/p[i];
            step=step*(p[i]-1);
            sol=sol*step;
        }
    }
    if(x>1) sol=sol*(x-1);
    return sol*2;
}
int main()
{
    int n;
    fin>>n;
    ciur(n);
    long long sol=0;
    for(int i=1;i<=n;i++)
    {
        sol+=desc(i);
    }
    fout<<sol-1;
}