Pagini recente » Cod sursa (job #632706) | Cod sursa (job #3174971) | Cod sursa (job #1846477) | Cod sursa (job #1913186) | Cod sursa (job #528133)
Cod sursa(job #528133)
#include<fstream>
#include<math.h>
using namespace std;
int f[1000],e[1000];
int main()
{
int n,i,x,d,nrf,j,p,n1,x2;
double rad,x1;
long long euler,sol=0;
ifstream fin("fractii.in");
fin>>n;
fin.close();
ofstream fout("fractii.out");
if(n==1) fout<<1<<"\n";
else
{
for(i=2;i<=n;i++)
{
nrf=0;
x=i;
if(x%2==0)
{
f[++nrf]=2;
while(x%2==0)
{
x=x/2;
e[nrf]++;
}
}
d=3;
while(x!=1)
{
if(x%d==0)
{
f[++nrf]=d;
while(x%d==0)
{
x=x/d;
e[nrf]++;
}
}
else
{
x1=x;
rad=sqrt(x1)+1;
while(x%d && d<rad)
d+=2;
if(d>rad) {f[++nrf]=x; e[nrf]=1; x=1;}
}
}
euler=1;
for(j=1;j<=nrf;j++)
{
p=1;
n1=e[j]-1;
x2=f[j];
while(n1>0)
{
if (n1 & 1)
{
p=p*x2;
n1--;
}
x2=x2*x2;
n1=n1>>1;
}
euler=euler*(f[j]-1)*p;
}
sol+=2*euler;
memset(e,0,sizeof(e));
}
}
fout<<sol+1<<"\n";
fout.close();
return 0;
}