Cod sursa(job #2204417)
Utilizator | Data | 15 mai 2018 19:00:01 | |
---|---|---|---|
Problema | Fractii | Scor | 30 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.53 kb |
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
#define MAXN 1000001
int totient[MAXN];
int main() {
freopen("fractii.in", "r", stdin);
freopen("fractii.out", "w", stdout);
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
totient[i] = i - 1;
}
int sum = 0;
for (int i = 2; i <= n; ++i) {
for (int j = i + i; j <= n; j += i) {
totient[j] -= totient[i];
}
sum += totient[i];
}
printf("\n%d", sum * 2 + 1);
return 0;
}