Cod sursa(job #187252)
Utilizator | Data | 2 mai 2008 15:41:23 | |
---|---|---|---|
Problema | Fractii | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.41 kb |
#include <stdio.h>
int main(){
FILE*in = fopen("fractii.in", "r");
FILE*out = fopen("fractii.out","w");
long i,n,j,phi[1000000] = {0};
long long s = 1;
fscanf ( in, "%ld", &n);
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];
for ( i = 2; i <= n;i++)
s += 2*phi[i];
fprintf (out, "%lld", s);
return 0;
}