Pagini recente » Cod sursa (job #793237) | Cod sursa (job #991516) | Cod sursa (job #521707) | Cod sursa (job #1847609) | Cod sursa (job #265904)
Cod sursa(job #265904)
#include <stdio.h>
#define LL unsigned long long
#define MAX_P 1000010
LL n, m, i;
LL prim[MAX_P / 10];
LL sol;
bool ciur[MAX_P], fol[MAX_P];
void calc_prim() {
for (i = 2; i < MAX_P; i++)
if (ciur[i] == 0) {
prim[++prim[0]] = i;
for (int j = i; j < MAX_P; j += i)
ciur[j] = 1;
}
}
void back(LL poz, LL fact, LL nr) {
if (!fol[fact] && nr) {
if (nr % 2 == 1)
sol += 1LL * (n / fact) * (m / fact);
else sol -= 1LL * (n / fact) * (m / fact);
fol[fact] = 1;
}
//folosesc divizorul prim[i]
if (1LL * fact * prim[poz] < n) back(poz + 1, fact * prim[poz], nr + 1);
else return;
back(poz + 1, fact, nr);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
scanf("%lld", &n);
n = m;
calc_prim();
n--; m--;
back(1, 1, 0);
if (!n) sol++;
if (!m) sol++;
printf("%lld\n", (LL) n * m + 2 - sol);
return 0;
}