Cod sursa(job #1874913)

Utilizator mircearoataMircea Roata Palade mircearoata Data 10 februarie 2017 16:01:39
Problema Fractii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <bitset>

using namespace std;

ifstream in("fractii.in");
ofstream out("fractii.out");

int n,z;
long long raspuns;
bitset<1000001> ciur;
int prime[78500];

int d[20],p[20];

void descompunere(int n)
{
    z=0;
    for(int i = 1; i<=78500 && ciur[n]==1; i++)
    {
        if(n%prime[i]==0)
        {
            z++;
            d[z]=prime[i];
            p[z]=0;
            while(n%prime[i]==0)
            {
                p[z]++;
                n/=prime[i];
            }
        }
    }
    if(n!=1)
    {
        z++;
        d[z]=n;
        p[z]=1;
    }
}

int pow(int a,int b)
{
    int p=1;
    for(int i = 1;i<=b;i++)
    {
        p*=a;
    }
    return p;
}

int euler(int n)
{
    descompunere(n);
    int rez=1;
    for(int i = 1;i<=z;i++)
    {
        rez*=(d[i]-1)*pow(d[i],p[i]-1);
    }
    return rez;
}
int main()
{
    in>>n;
    for(int i = 2; i<=n; i++)
    {
        if(ciur[i]==0)
        {
            z++;
            prime[z]=i;
            for(int j = 2; j<=n/i; j++)
            {
                ciur[i*j]=1;
            }
        }
    }
    raspuns=1;
    for(int i = n; i>=2; i--)
    {
        raspuns+=2*euler(i);
    }
    out<<raspuns;
    return 0;
}