Cod sursa(job #407944)
Utilizator | Vlad Tarniceru vladtarniceru | Data | 2 martie 2010 19:03:47 |
---|---|---|---|
Problema | Fractii | Scor | 30 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.63 kb |
#include<fstream.h>
ifstream f("fractii.in");
ofstream g("fractii.out");
int phi(long n){
long v[100001],i,j,s=1;
v[1]=1;
for(i=1;i<=n;i++) v[i]=i-1;
for(i=2;i<=n;i++)
for(j=i*2;j<=n;j+=i)
v[j]-=v[i];
/*for (int i = 1; i <= N; ++i)
v[i] = i-1;
for (int i = 2; i <= N; ++i)
for (int j = 2*i; j <= N; j += i)
v[j] -= v[i];*/
for(i=1;i<=n;i++) s+=v[i];
return s;//g<<s*2-1<<"\n";
}
int main(){
long n;
f>>n;
//g<<n;
phi(n);
g<<phi(n)*2-1;
g.close();
return 0;
}