Cod sursa(job #220354)
Utilizator | Data | 10 noiembrie 2008 15:49:25 | |
---|---|---|---|
Problema | Fractii | Scor | 30 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.48 kb |
#include<fstream.h>
#include<iostream.h>
int n,w,i,f[100],x,q,phi;
long long s;
int main()
{
ifstream in("fractii.in");
ofstream out("fractii.out");
in>>x;
for(n=1;n<=x;n++)
{
q=0;
w=n;
for(i=2;i*i<=n && w!=1;++i)
{
if(w%i==0)
{
q++;
f[q]=i;
while(w%i==0) w=w/i;
}
}
if(w!=1) f[++q]=w;
phi=n;
for(i=1;i<=q;i++)
phi=(phi*(f[i]-1))/f[i];
s=s+(2*phi);
}
out<<s-1<<endl;
return 0;
}