Cod sursa(job #416793)
Utilizator | Data | 13 martie 2010 15:47:55 | |
---|---|---|---|
Problema | Fractii | Scor | 30 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.52 kb |
#include <stdio.h>
#include <math.h>
#define nmax 1000000
using namespace std;
int n, nrt, phi[nmax];
void citire ()
{
scanf("%d",&n);
}
void solve ()
{
for (int i = 1; i <= n; i++)
phi[i]=i;
for (int i = 2; i<=n ; i++)
if (phi[i]==i)
for (int j = i;j <= n; j += i) phi[j] /=i, phi[j] *= (i-1);
}
int main ()
{
freopen("fractii.in","r",stdin);
freopen("fractii.out","w",stdout);
citire ();
solve ();
nrt = 1;
for (int i = 2; i <= n; i++)
nrt += phi[i] *2;
printf("%d",nrt);
}