Cod sursa(job #732834)
Utilizator | Data | 11 aprilie 2012 01:26:36 | |
---|---|---|---|
Problema | Fractii | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.56 kb |
#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;
int Phi[1000002];
ifstream f("fractii.in");
ofstream g("fractii.out");
long long int Nr(int N)
{
long long Nr=0;
int i,j;
for (i=1; i<=N; i++)
Phi[i]=i-1;
for (i=2; i<=N; i++)
for (j=2; j*i<=N; j++)
Phi[i*j]-=Phi[i];
for (i=2; i<=N; i++)
Nr+=2*Phi[i];
return Nr;
}
int main()
{
int N;
f>>N;
g<<Nr(N)+1;
f.close();
g.close();
return 0;
}