Cod sursa(job #1150219)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 22 martie 2014 17:58:49
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include<fstream>
#include<iostream>
using namespace std;
int phi[1000020];
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];

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

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