Pagini recente » Cod sursa (job #2867377) | Cod sursa (job #3030285) | Cod sursa (job #2926153) | Cod sursa (job #982439) | Cod sursa (job #1874913)
#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
ifstream in("fractii.in");
ofstream out("fractii.out");
int n,z;
long long raspuns;
bitset<1000001> ciur;
int prime[78500];
int d[20],p[20];
void descompunere(int n)
{
z=0;
for(int i = 1; i<=78500 && ciur[n]==1; i++)
{
if(n%prime[i]==0)
{
z++;
d[z]=prime[i];
p[z]=0;
while(n%prime[i]==0)
{
p[z]++;
n/=prime[i];
}
}
}
if(n!=1)
{
z++;
d[z]=n;
p[z]=1;
}
}
int pow(int a,int b)
{
int p=1;
for(int i = 1;i<=b;i++)
{
p*=a;
}
return p;
}
int euler(int n)
{
descompunere(n);
int rez=1;
for(int i = 1;i<=z;i++)
{
rez*=(d[i]-1)*pow(d[i],p[i]-1);
}
return rez;
}
int main()
{
in>>n;
for(int i = 2; i<=n; i++)
{
if(ciur[i]==0)
{
z++;
prime[z]=i;
for(int j = 2; j<=n/i; j++)
{
ciur[i*j]=1;
}
}
}
raspuns=1;
for(int i = n; i>=2; i--)
{
raspuns+=2*euler(i);
}
out<<raspuns;
return 0;
}