/* -*- coding: utf-8 -*- * * 3687.cc: No.3687 Coprime Count - yukicoder */ #include #include using namespace std; /* constant */ const int MAX_N = 10000000; /* typedef */ using ll = long long; /* global variables */ bool primes[MAX_N + 1]; int pds[MAX_N + 1], myus[MAX_N + 1]; /* subroutines */ void gen_primes(int maxp) { fill(primes, primes + maxp + 1, true); primes[0] = primes[1] = false; fill(pds, pds + maxp + 1, 0); pds[1] = 1; int p; for (p = 2; p * p <= maxp; p++) if (primes[p]) { pds[p] = p; for (int q = p * p; q <= maxp; q += p) { primes[q] = false; if (! pds[q]) pds[q] = p; } } for (; p <= maxp; p++) if (primes[p]) pds[p] = p; } /* main */ int main() { int n, m; scanf("%d%d", &n, &m); if (n > m) swap(n, m); gen_primes(MAX_N); myus[1] = 1; for (int i = 2; i <= n; i++) { int j = i / pds[i]; if (j % pds[i] == 0) myus[i] = 0; else myus[i] = -myus[j]; } ll sum = 0; for (int d = 1; d <= n; d++) if (myus[d] != 0) sum += (ll)myus[d] * (n / d) * (m / d); printf("%lld\n", sum); return 0; }