Cod sursa(job #2742539)
Utilizator | Vlad Tutunaru vlad2009 | Data | 21 aprilie 2021 10:03:46 |
---|---|---|---|
Problema | Fractii | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.48 kb |
#include <fstream>
#define NM 1000002
using namespace std;
int phi[NM];
int main()
{
ifstream fin("fractii.in");
ofstream fout("fractii.out");
long long rez = 1;
int n;
fin >> n;
phi[1] = 1;
for (int i = 2; i <= n; i++)
{
int k = 1;
phi[i] += i - 1;
rez += phi[i];
for (int j = 2; i * j <= n; j++)
{
phi[i * j] -= phi[i];
}
}
fout << rez * 2 - 1;
return 0;
}