Cod sursa(job #283943)
Utilizator | Anusca Andrei deviance | Data | 20 martie 2009 20:14:51 |
---|---|---|---|
Problema | Fractii | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.51 kb |
#include<fstream.h>
#include<math.h>
long a[1000001],n,i,ii,j,x,y,q,m,ok;
long long nr,r;
int main()
{
ifstream f("fractii.in");
ofstream g("fractii.out");
f>>n;
a[1]=1;
for(i=2;i<=n;i++)
{x=i;
q=2;
r=sqrt(x);
while(q<=r && x%q)q++;
if(q>r)a[i]=i-1;
else
{
y=1;
while(x%q==0){y=y*q;
x=x/q;
}
y=y/q;
a[i]=(q-1)*y*a[x];
}
}
nr=1;
for(i=2;i<=n;i++)
nr=nr+2*a[i];
g<<nr;
g.close();
return 0;
}