Pagini recente » Cod sursa (job #43406) | Cod sursa (job #684244) | Cod sursa (job #1355770) | Cod sursa (job #1061352) | Cod sursa (job #388014)
Cod sursa(job #388014)
#include <iostream>
#include <cstdlib>
#include <bitset>
#include <vector>
using namespace std;
#define maxN 1000100
#define pb push_back
#define bit(i, x) (((i) >> x) & 1)
int N, M, mx;
long long Sol = 2;
bitset< maxN > Prime;
vector<int> Primes;
void get_divs( ) {
int i, j, maxI = max(N, M);
Prime.set(); Prime[0] = Prime[1] = false;
for (i = 4; i <= maxI; i += 2)
Prime[i] = false;
Primes.push_back(2);
for (i = 3; i <= maxI; i += 2)
if (Prime[i]) {
Primes.push_back(i);
for (j = i + i; j <= maxI; j += i)
Prime[j] = false;
}
}
void backtrk(int P, int X, int Val, int Nr) {
if (P == X || 1LL * Val * Primes[P] > 1LL * mx) {
if (Nr % 2 == 0)
Sol += 1LL * (M / Val) * (N / Val);
else Sol -= 1LL * (M / Val) * (N / Val);
return;
}
backtrk(P + 1, X, Val, Nr);
backtrk(P + 1, X, Val * Primes[P], Nr + 1);
}
int main( ) {
int i, j;
scanf("%d%d", &N, &M);
if (N == 1 && M == 1) {
printf("0\n");
return 0;
}
if (N == 1 || M == 1) {
printf("1\n");
return 0;
}
get_divs(); M --; N --; mx = (N < M) ? N : M;
backtrk(0, Primes.size(), 1, 0);
cout << Sol - 2<< "\n";
}