Cod sursa(job #1130205)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 28 februarie 2014 11:52:48
Problema Fractii Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>
#include <vector>

using namespace std;

vector<int> f, e;
int N;

void descompune(int x);
int Euler();
int put(int a, int b);

int main()
{
    freopen("fractii.in", "r", stdin);
    freopen("fractii.out", "w", stdout);

    scanf("%d",&N);

    int nr_fr=1, cnt=2;

    while(cnt<=N)
    {
        descompune(cnt);
        nr_fr+=2*Euler();
        f.clear();
        e.clear();
        cnt++;
    }

    printf("%d",nr_fr);

    return 0;
}

void descompune(int x)
{
    int ex=0, i=2;
    while(x!=1)
    {
        ex=0;
        while(x%i==0)
        {
            x/=i;
            ex++;
        }
        f.push_back(i);
        e.push_back(ex);
        i++;
    }
}

int Euler()
{
    int indEuler=1;
    for(int i=0; i<f.size(); i++)
    if(e[i])
    {
        indEuler*=(f[i]-1)*put(f[i], e[i]-1);
    }
    return indEuler;
}

inline int put(int a, int b)
{
    int ca=a;
    if(b == 0) return 1;
    for(int i=1; i<b; i++) a*=ca;
    return a;
}