Cod sursa(job #16779)
| Utilizator | Data | 13 februarie 2007 23:52:12 | |
|---|---|---|---|
| Problema | Fractii | Scor | 100 |
| Compilator | c | Status | done |
| Runda | Arhiva de probleme | Marime | 0.45 kb |
#include <stdio.h>
#define MAXN (1 << 20)
int N;
long long rez;
int cnt[MAXN];
int main(void)
{
freopen("fractii.in", "rt", stdin);
freopen("fractii.out", "wt", stdout);
int i, j;
scanf("%d\n", &N);
for(i = 2; i <= N; i++)
{
cnt[i] = i-1-cnt[i];
for(j = 2; j*i <= N; j++)
cnt[i*j] += cnt[i];
}
for(i = 2; i <= N; i++)
rez += (long long)cnt[i]*2;
rez++;
printf("%lld\n", rez);
return 0;
}
