Cod sursa(job #121825)
| Utilizator | Data | 9 ianuarie 2008 21:57:40 | |
|---|---|---|---|
| Problema | Fractii | Scor | 100 |
| Compilator | c | Status | done |
| Runda | Arhiva de probleme | Marime | 0.43 kb |
#include <stdio.h>
long long int phi[1000000],n,sol=1;
long long int phii(long long 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 main() {
long long int i;
freopen("fractii.in","r",stdin);
freopen("fractii.out","w",stdout);
scanf("%lld",&n);
phii(n);
for (i=2;i<=n;i++)
sol+=2*phi[i];
printf("%lld",sol);
return 0;
}
