Cod sursa(job #3219542)
Utilizator | Stefan Dore stefan_dore_ | Data | 31 martie 2024 16:53:25 |
---|---|---|---|
Problema | Fractii | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.58 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("fractii.in");
ofstream g ("fractii.out");
const int NMAX = 1000000;
int Phi[NMAX+1];
void euler(int NMAX) {
int i, j;
for (i=1; i<=NMAX; i++)
Phi[i] = i;
for (i=2; i<=NMAX; i++)
if (Phi[i]==i)
for(j=i; j<=NMAX; j+=i)
Phi[j] -= Phi[j]/i;
}
int main()
{
int N, sol;
f >> N;
euler(NMAX);
for (int i=2; i<=N; i++)
sol += Phi[i];
sol = sol*2 + 1;
g << sol;
f.close();
g.close();
return 0;
}