#include "stdio.h"
#include "math.h"
#define MAXSIZE 1000000/2/8+1
char prim[MAXSIZE];
int t[1000001];
int ProcessDivisors(unsigned int r, int m, unsigned divizor[10])
{
int k = m;
switch(r)
{
case 1:
{
k -= m/divizor[0];
return k;
}
case 2:
{
k = k - m/divizor[0] - m/divizor[1] + m / (divizor[0] * divizor[1]);
return k;
}
case 3:
{
int p1 = divizor[0], p2 = divizor[1], p3 = divizor[2];
k = k - m/p1 - m/p2 - m/p3 + m/(p1*p2) + m/(p1*p3) + m/(p2*p3) - m/(p1*p2*p3);
return k;
}
case 4:
{
int p1 = divizor[0], p2 = divizor[1], p3 = divizor[2], p4 = divizor[3];
k = k - m/p1 - m/p2 - m/p3 - m/p4 + m/(p1*p2) + m/(p1*p3) + m/(p1*p4) + m/(p2*p3) + m/(p2*p4) + m / (p3*p4) - m/(p1*p2*p3) - m/(p1*p2*p4) - m/(p1*p3*p4) - m/(p2*p3*p4) + m/(p1*p2*p3*p4);
return k;
}
case 5:
{
int p1 = divizor[0], p2 = divizor[1], p3 = divizor[2], p4 = divizor[3], p5 = divizor[4];
k = k - m/p1 - m/p2 - m/p3 - m/p4 -m/p5 + m/(p1*p2) + m/(p1*p3) + m/(p1*p4) + m/(p1*p5) + m/(p2*p3) + m/(p2*p4) + m/(p2*p5) + m / (p3*p4) + m/(p3*p5) + m/(p4*p5) - m/(p1*p2*p3) - m/(p1*p2*p4) - m/(p1*p2*p5) - m/(p1*p3*p4) - m/(p1*p3*p5) - m/(p1*p4*p5) - m/(p2*p3*p4) - m/(p2*p3*p5) - m/(p2*p4*p5) - m/(p3*p4*p5);
k = k + m/(p1*p2*p3*p4) + m/(p1*p2*p3*p5) + m/(p1*p2*p4*p5) + m/(p1*p3*p4*p5) + m/(p2*p3*p4*p5) - m/(p1*p2*p3*p4*p5);
return k;
}
case 6:
{
int p1 = divizor[0], p2 = divizor[1], p3 = divizor[2], p4 = divizor[3], p5 = divizor[4], p6 = divizor[5];
k = k - m/p1 - m/p2 - m/p3 - m/p4 - m/p5 - m/p6;
k = k + m/(p1*p2) + m/(p1*p3) + m/(p1*p4) + m/(p1*p5) + m/(p1*p6) + m/(p2*p3) + m/(p2*p4) + m/(p2*p5) + m/(p2*p6) + m/(p3*p4) + m/(p3*p5) + m/(p3*p6) + m/(p4*p5) + m/(p4*p6) + m/(p5*p6);
k = k - m/(p1*p2*p3) - m/(p1*p2*p4) - m/(p1*p2*p5) - m/(p1*p2*p6) - m/(p1*p3*p4) - m/(p1*p3*p5) - m/(p1*p3*p6) - m/(p1*p4*p5) - m/(p1*p4*p6) - m/(p1*p5*p6) - m/(p2*p3*p4) - m/(p2*p3*p5) - m/(p2*p3*p6) - m/(p2*p4*p5) - m/(p2*p4*p6) - m/(p2*p5*p6) - m/(p3*p4*p5) - m/(p3*p4*p6) - m/(p3*p5*p6) - m/(p4*p5*p6);
k = k + m/(p1*p2*p3*p4) + m/(p1*p2*p3*p5) + m/(p1*p2*p3*p6) + m/(p1*p2*p4*p5) + m/(p1*p2*p4*p6) + m/(p1*p2*p5*p6) + m/(p1*p3*p4*p5) + m/(p1*p3*p4*p6) + m/(p1*p3*p5*p6) + m/(p1*p4*p5*p6) + m/(p2*p3*p4*p5) + m/(p2*p3*p4*p6) + m/(p2*p3*p5*p6) + m/(p2*p4*p5*p6) + m/(p3*p4*p5*p6);
k = k - m/(p1*p2*p3*p4*p5) - m/(p1*p2*p3*p4*p6) - m/(p6*p2*p3*p4*p5) - m/(p1*p6*p3*p4*p5) - m/(p1*p2*p6*p4*p5) - m/(p1*p2*p3*p6*p5) + m/(p1*p2*p3*p4*p5*p6);
return k;
}
case 7:
{
const int C71[7] = {0, 1, 2, 3, 4, 5, 6};
const int C72[21][2] = {
{0, 1},
{0, 2},
{0, 3},
{0, 4},
{0, 5},
{0, 6},
{1, 2},
{1, 3},
{1, 4},
{1, 5},
{1, 6},
{2, 3},
{2, 4},
{2, 5},
{2, 6},
{3, 4},
{3, 5},
{3, 6},
{4, 5},
{4, 6},
{5, 6}
};
const int C73[35][3] = {
{0, 1, 2},
{0, 1, 3},
{0, 1, 4},
{0, 1, 5},
{0, 1, 6},
{0, 2, 3},
{0, 2, 4},
{0, 2, 5},
{0, 2, 6},
{0, 3, 4},
{0, 3, 5},
{0, 3, 6},
{0, 4, 5},
{0, 4, 6},
{0, 5, 6},
{1, 2, 3},
{1, 2, 4},
{1, 2, 5},
{1, 2, 6},
{1, 3, 4},
{1, 3, 5},
{1, 3, 6},
{1, 4, 5},
{1, 4, 6},
{1, 5, 6},
{2, 3, 4},
{2, 3, 5},
{2, 3, 6},
{2, 4, 5},
{2, 4, 6},
{2, 5, 6},
{3, 4, 5},
{3, 4, 6},
{3, 5, 6},
{4, 5, 6}
};
const int C74[35][4] = {
{0, 1, 2, 3},
{0, 1, 2, 4},
{0, 1, 2, 5},
{0, 1, 2, 6},
{0, 1, 3, 4},
{0, 1, 3, 5},
{0, 1, 3, 6},
{0, 1, 4, 5},
{0, 1, 4, 6},
{0, 1, 5, 6},
{0, 2, 3, 4},
{0, 2, 3, 5},
{0, 2, 3, 6},
{0, 2, 4, 5},
{0, 2, 4, 6},
{0, 2, 5, 6},
{0, 3, 4, 5},
{0, 3, 4, 6},
{0, 3, 5, 6},
{0, 4, 5, 6},
{1, 2, 3, 4},
{1, 2, 3, 5},
{1, 2, 3, 6},
{1, 2, 4, 5},
{1, 2, 4, 6},
{1, 2, 5, 6},
{1, 3, 4, 5},
{1, 3, 4, 6},
{1, 3, 5, 6},
{1, 4, 5, 6},
{2, 3, 4, 5},
{2, 3, 4, 6},
{2, 3, 5, 6},
{2, 4, 5, 6},
{3, 4, 5, 6}
};
const int C75[21][5] = {
{0, 1, 2, 3, 4},
{0, 1, 2, 3, 5},
{0, 1, 2, 3, 6},
{0, 1, 2, 4, 5},
{0, 1, 2, 4, 6},
{0, 1, 2, 5, 6},
{0, 1, 3, 4, 5},
{0, 1, 3, 4, 6},
{0, 1, 3, 5, 6},
{0, 1, 4, 5, 6},
{0, 2, 3, 4, 5},
{0, 2, 3, 4, 6},
{0, 2, 3, 5, 6},
{0, 2, 4, 5, 6},
{0, 3, 4, 5, 6},
{1, 2, 3, 4, 5},
{1, 2, 3, 4, 6},
{1, 2, 3, 5, 6},
{1, 2, 4, 5, 6},
{1, 3, 4, 5, 6},
{2, 3, 4, 5, 6}
};
const int C76[7][6] = {
{0, 1, 2, 3, 4, 5},
{0, 1, 2, 3, 4, 6},
{0, 1, 2, 3, 5, 6},
{0, 1, 2, 4, 5, 6},
{0, 1, 3, 4, 5, 6},
{0, 2, 3, 4, 5, 6},
{1, 2, 3, 4, 5, 6}
};
int i,j, val = 0;
for(j=0; j<7; j++)
val += m/divizor[C71[j]];
k -= val;
val = 0;
for(i=0; i<21; i++)
{
int temp = 1;
for(j=0; j<2; j++)
temp *= divizor[C72[i][j]];
val += m/temp;
}
k += val;
val = 0;
for(i=0; i<35; i++)
{
int temp = 1;
for(j=0; j<3; j++)
temp *= divizor[C73[i][j]];
val += m/temp;
}
k -= val;
val = 0;
for(i=0; i<35; i++)
{
int temp = 1;
for(j=0; j<4; j++)
temp *= divizor[C74[i][j]];
val += m/temp;
}
k += val;
val = 0;
for(i=0; i<21; i++)
{
int temp = 1;
for(j=0; j<5; j++)
temp *= divizor[C75[i][j]];
val += m/temp;
}
k -= val;
val = 0;
for(i=0; i<7; i++)
{
int temp = 1;
for(j=0; j<6; j++)
temp *= divizor[C76[i][j]];
val += m/temp;
}
k += val;
k = k - m/(divizor[0]*divizor[1]*divizor[2]*divizor[3]*divizor[4]*divizor[5]*divizor[6]);
return k;
}
default:
{
return k;
}
}
}
int main(void)
{
FILE *fin, *fout;
if((fin = fopen("fractii.in", "r"))==NULL)
return 0;
if((fout = fopen("fractii.out", "w"))==NULL)
return 0;
unsigned int N, mod, r;
unsigned long long n, fi;
unsigned int divizor[10];
fscanf(fin, "%d", &N);
n = N;
//p[i] == 0 if 2*i + 1 is prime
unsigned int i, j;
for (i = 1; ((i * i) << 1) + (i << 1) <= n; i += 1)
{
if ((prim[i >> 3] & (1 << (i & 7))) == 0)
{
for (j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= n; j += (i << 1) + 1)
{
prim[j >> 3] |= (1 << (j & 7));
}
}
}
t[1] = t[2] = 1;
unsigned long long d = 2;
while(d<=N)
{
t[d] = (int)d/2;
d *= 2;
}
for(i=3; i<=N; i+=2)
{
int temp = (i-1)/2;
if ((prim[temp >> 3] & (1 << (temp & 7))) == 0)
{
t[i] = i-1;
unsigned long long k = i;
while(k<=N)
{
t[k] = (i-1)*((int)k/i);
k *= i;
}
}
}
for(i=3; i<=N; i++)
{
if(t[i] == 0)
{
if(i%2 == 0)
{
r = 0;
unsigned int p = i;
while(p % 2 == 0)
{
p = p/2;
r++;
if(p == 1)
break;
}
if(r>0 && t[p] != 0 && p%2!=0)
{
t[i] = t[p];
for(unsigned int k=1; k<=r-1; k++)
t[i] *= 2;
}
}
if(t[i] == 0)
{
for(j=3; j<=i; j+=2)
{
int temp = (j-1)/2;
if ((prim[temp >> 3] & (1 << (temp & 7))) == 0)
{
int p = i;
r = 0;
while(p%j==0)
{
p = p/j;
r++;
}
if(r>0 && t[p] != 0 && p%j!=0)
{
t[i] = t[p]*(j-1);
for(unsigned int k=1; k<=r-1; k++)
t[i] *= j;
break;
}
}
}
}
}
}
n=N;
for(i=2; i<=N; i++)
{
fi = t[i];
mod = N%i;
fi *= N/i;
if(mod != 0)
{
if(i<=2 || (i%2==1 && (prim[((i-1)/2) >> 3] & (1 << (((i-1)/2) & 7))) == 0))
fi += mod;
else
{
r=0;
unsigned int p=i;
if(p%2 == 0)
{
while(p%2==0)
p = p/2;
divizor[r++] = 2;
}
if(p != 1)
{
if(p%2==1 && (prim[((p-1)/2) >> 3] & (1 << (((p-1)/2) & 7))) == 0)
{
if(p<=mod)
divizor[r++] = p;
}
else
{
unsigned int sqr = (unsigned int)sqrt((double)i);
if(mod <= sqr)
{
for(j=3; j<=mod; j+=2)
{
if(p%j == 0)
{
int temp = (j-1)/2;
if((prim[temp >> 3] & (1 << (temp & 7))) == 0)
{
while(p%j==0)
p = p/j;
divizor[r++] = j;
if(p==1 || (p%2==1 && (prim[((p-1)/2) >> 3] & (1 << (((p-1)/2) & 7))) == 0))
{
if(p> 2 && p<=mod)
divizor[r++] = p;
break;
}
}
}
}
}
else
{
for(j=3; j<=sqr; j+=2)
{
if(p%j == 0)
{
int temp = (j-1)/2;
if((prim[temp >> 3] & (1 << (temp & 7))) == 0)
{
while(p%j==0)
p = p/j;
divizor[r++] = j;
if(p==1 || (p%2==1 && (prim[((p-1)/2) >> 3] & (1 << (((p-1)/2) & 7))) == 0) )
{
if((p> 2 && p<=mod))
divizor[r++] = p;
break;
}
}
}
}
}
}
}
if(r==0)
fi += mod;
else
fi += ProcessDivisors(r, mod, divizor);
}
}
n+=fi;
}
fprintf(fout, "%llu", n);
fclose(fin);
fclose(fout);
return 0;
}
Airinei Vasile airineiv