Cod sursa(job #329756)
Utilizator | Gagos Radu Vasile Gagos | Data | 7 iulie 2009 13:58:05 |
---|---|---|---|
Problema | Fractii | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.44 kb |
#include<cstdio>
#define nmax 1000005
using namespace std;
int tot[nmax],n,i,j,x;
long long s;
int main()
{
freopen("fractii.in","r",stdin);
freopen("fractii.out","w",stdout);
scanf("%lld",&n);
memeset(tot,0,sizeof(tot));
for(i=2;i<=n;++i)
tot[i]=i-1;
for(i=2;i<=n;++i)
{
x=i<<2;
while(x<=n)
{
tot[x]-=tot[i];
x+=i;
}
s+=tot[i];
}
s=(s<<1)|1;
printf("%lld\n",s);
return 0;
}