Cod sursa(job #3301348)
| Utilizator | Data | 25 iunie 2025 10:16:49 | |
|---|---|---|---|
| Problema | Fractii | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 0.58 kb |
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("fractii.in");
ofstream cout("fractii.out");
vector<int> phi;
void phi_1_n(int n) {
phi.resize(n + 2);
for (int i = 1 ; i <= n ; ++i) phi[i] = i;
for (int i = 2 ; i <= n ; ++i) {
if (phi[i] == i) {
for (int j = i ; j <= n ; j += i) {
phi[j] -= phi[j] / i;
}
}
}
}
int main() {
int n;
cin >> n;
phi_1_n(n);
long long sum = 0;
for (int i = 1 ; i <= n ; ++i) {
sum += 2 * phi[i];
}
cout << sum - 1;
return 0;
}