Pagini recente » Cod sursa (job #1686580) | Cod sursa (job #794985) | Cod sursa (job #2097708) | Cod sursa (job #557595) | Cod sursa (job #2228541)
#include <stdio.h>
using namespace std;
const int NMAX = 1000000,
PMAX = 78498;
int n, m, minn,
nrP = 1, sE,
p[PMAX+2];
char b[NMAX+1];
long long cnt;
void bt(int v, int pr) {
if(sE & 1) cnt -= 1LL * (n/v) * (m/v);
else cnt += 1LL * (n/v) * (m/v);
for(int i = pr; i <= nrP; i++) {
if(v <= minn/p[i]) {
sE++;
bt(v * p[i], i+1);
sE--;
} else return;
}
}
void ciur(int x) {
for(int i = 4; i <= x; i += 2)
b[i] = 1;
for(int i = 3; i * i <= x; i += 2)
if(b[i] == 0)
for(int j = i*i; j <= x; j += i)
b[j] = 1;
p[1] = 2;
for(int i = 3; i <= x; i += 2)
if(b[i] == 0) p[++nrP] = i;
}
int main()
{
freopen("mins.in", "r", stdin);
freopen("mins.out", "w", stdout);
scanf("%i %i", &n, &m);
n--, m--;
minn = (m > n) ? n : m;
ciur(minn);
bt(1, 1);
printf("%lld", cnt);
return 0;
}