Cod sursa(job #216380)
Utilizator | Silvia Pripoae silvia_the_best | Data | 24 octombrie 2008 10:46:34 |
---|---|---|---|
Problema | Fractii | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.47 kb |
#include <cstdio>
#define N 1000000
int n,e[N];
void read(){
freopen("fractii.in","r",stdin);
scanf("%d",&n);
}
void solve(){
int i,j;
for (i=1;i<=n;++i)
e[i]=i;
for (i=2;i<=n;++i)
if (e[i]==i)
{
--e[i];
for (j=i+i;j<=n;j+=i)
e[j]=e[j]*(i-1)/i;
}
}
void write(){
int i;
long long sum=1;
freopen("fractii.out","w",stdout);
for (i=2;i<=n;++i)
sum+=2*e[i];
printf("%lld\n",sum);
}
int main(){
read();
solve();
write();
}