Cod sursa(job #2414499)
| Utilizator | Data | 24 aprilie 2019 17:11:18 | |
|---|---|---|---|
| Problema | Fractii | Scor | 30 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 0.51 kb |
#include <cstdio>
using namespace std;
const int NMAX = 1000005;
int phi[NMAX];
int main()
{
freopen("fractii.in","r",stdin);
freopen("fractii.out","w",stdout);
int n;
scanf("%d",&n);
for(int i = 2 ; i <= n ; i++)
phi[i] = i-1;
for(int i = 2 ; i <= n/2 ; i++)
for(int j = 2 * i ; j <= n ; j += i)
phi[j] -= phi[i];
int ans = 0;
for(int i = 2 ; i <= n ; i++)
ans = ans + phi[i];
printf("%d\n",(ans<<1)+1);
return 0;
}
