Pagini recente » Cod sursa (job #167027) | Cod sursa (job #655415) | Cod sursa (job #777110) | Cod sursa (job #1499212) | Cod sursa (job #1694519)
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 1000505;
int N, M, cntPrimeFactors[NMAX];
bool hasSquareFactor[NMAX];
int main() {
freopen("mins.in", "r", stdin);
freopen("mins.out", "w", stdout);
scanf("%d%d", &N, &M);
N--; M--;
if (N > M) {
swap(N, M);
}
for (int i = 2; i <= N; i++) {
if (!cntPrimeFactors[i]) {
cntPrimeFactors[i] = 1;
for (int j = 2 * i; j <= N; j += i) {
cntPrimeFactors[j]++;
if (j % (1LL * i * i) == 0) {
hasSquareFactor[j] = true;
}
}
}
}
long long res = 1LL * N * M;
// now deduct bad pairs i.e. (i, j) s.t. gcd(i, j) > 1
for (int d = 2; d <= N; d++) {
if (!hasSquareFactor[d]) {
int sign = (cntPrimeFactors[d] & 1) ? 1 : -1;
// pairs with both coordinates multiple of d
res -= sign * (N / d) * (M / d);
}
}
printf("%lld\n", res);
return 0;
}