Cod sursa(job #1150217)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 22 martie 2014 17:51:09
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<fstream>
#include<iostream>
using namespace std;
int phi[1000001];
void euler(int n)
{
    int i,j;
    for( i = 1 ; i<=n ; i++)
        phi[i] = i-1;
    for(i = 2 ; i<= n ; i++)
        for( j = 2*i ; j <=n ; j+=i)
            phi[j]-=phi[i];

}
int calculeaza(int n)
{
    int sol = 0;
    for(int i = 1 ; i<=n ; i++)
        sol+=phi[i];
    return sol;
}

int main()
{
    ifstream in("fractii.in");
    ofstream out("fractii.out");
    int n,k;
    in>>n;
    euler(n);
    k = calculeaza(n);
    out<<2*k+1;
    in.close();
    out.close();
    return 0;
}