Cod sursa(job #2299717)
| Utilizator | Data | 9 decembrie 2018 21:58:23 | |
|---|---|---|---|
| Problema | Fractii | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 0.63 kb |
#include <iostream>
#include <fstream>
#define NUM 1000005
int phi[NUM];
int n;
long long sum;
using namespace std;
int main()
{
ifstream f("fractii.in");
ofstream g("fractii.out");
f >> n;
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] * (1 - 1 / i)
phi[j] /= i;
phi[j] *= (i - 1);
}
for(int i = 2; i <= n; ++i)
{
sum += phi[i];
}
g << 1 + 2 * sum;
f.close();
g.close();
}
