Cod sursa(job #2148903)
Utilizator | Data | 2 martie 2018 09:38:49 | |
---|---|---|---|
Problema | Fractii | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.69 kb |
#include <fstream>
using namespace std;
int v[1000007];
int n,i,k,j,x;
int main()
{ ifstream cin("fractii.in");
ofstream cout("fractii.out");
cin>>n;
for(i=2; i<=n; i++)
if(v[i]==0)
{
v[i]=i-1;
for(j=2*i; j<=n; j+=i)
{
if(!v[j])v[j]=1;
k=1;
x=j/i;
while(x%i==0)
{
k*=i;;
x/=i;
}
v[j]=v[j]*(i-1)*k;
}
}
long long s=1;
for(i=2; i<=n; i++)
s+=2*v[i];
// cout<<i<<" "<<v[i]<<endl;
cout<<s;
return 0;
}