Pagini recente » Florian Marcu | Istoria paginii utilizator/porc_dumitru | Profil Asgari_Armin | Istoria paginii utilizator/flavialice | Cod sursa (job #528055)
Cod sursa(job #528055)
#include<fstream>
#include<math.h>
#include<iostream>
using namespace std;
int f[1000],e[1000];
int RidicareLaPutere(int x,int n)
{
int p=1;
while(n>0)
{
if (n & 1) // n este impar
{
p=p*x;
n--;
}
x=x*x;
n=n>>1; // sau n = n / 2
}
return p ;
}
int main()
{
clock_t start,stop;
start=clock();
int n,i,x,d,nrf,j;
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++)
{
euler=euler*(f[j]-1)*RidicareLaPutere(f[j],e[j]-1);
}
sol+=2*euler;
//memset(f,0,sizeof(f));
memset(e,0,sizeof(e));
nrf=0;
}
}
fout<<sol+1<<"\n";
fout.close();
stop=clock();
cout<<(double)(stop-start)/CLOCKS_PER_SEC<<"\n";
return 0;
}