Cod sursa(job #2003257)
| Utilizator | Data | 22 iulie 2017 15:12:05 | |
|---|---|---|---|
| Problema | Fractii | Scor | 90 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.56 kb |
#include <cstdio>
#define LL long long
#define MAX 1000000
using namespace std;
LL phi[MAX+5];
int n;
void getPhi()
{
for (int i=1; i<=n; i++)
phi[i]=i-1;
for (int i=1; i<=n; i++)
for (int j=2*i; j<=n; j+=i)
phi[j]-=phi[i];
}
int main()
{
freopen("fractii.in","r",stdin);
freopen("fractii.out","w",stdout);
scanf("%d",&n);
getPhi();
LL rez=0;
for (int numarator=1; numarator<=n; numarator++)
rez+=phi[numarator];
rez=rez*2+1;
printf("%lld",rez);
return 0;
}
