Cod sursa(job #1700484)
Utilizator | Andrei Florin Sburly | Data | 10 mai 2016 16:58:16 |
---|---|---|---|
Problema | Fractii | Scor | 90 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.52 kb |
/********************
Created by Sburly
********************/
#include <fstream>
using namespace std;
long long int totient[1000001];
long long int sol = 0;
long long int n, i, j;
int main()
{
ifstream f("fractii.in");
ofstream g("fractii.out");
f >> n;
for (i = 1; i <= n; i++)
totient[i] = i-1;
for (i = 2; i <= n; i++)
{
sol+=totient[i];
for (j = 2*i; j <= n; j += i)
totient[j] -= totient[i];
}
g << sol*2+1;
return 0;
}