Cod sursa(job #1529184)

Utilizator tudorcomanTudor Coman tudorcoman Data 20 noiembrie 2015 16:29:07
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxN = 1e6;

int N, M;
ll ans, lim;
int d[maxN + 2];
bool b[maxN + 2];

int main() {
  freopen("mins.in", "r", stdin);
  freopen("mins.out", "w", stdout);
  scanf("%d %d", &N, &M); -- N; -- M;
  lim = max(N, M);

  /// i = 2
  d[2] = 1;
  for(register int j = 4; j <= lim; j += 2)
    d[j] = 1;
  for(register ll j = 4; j <= lim; j += 4)
    b[j] = true;

  /// i = impar
  for(register ll i = 3; i <= lim; i += 2) {
    if(!d[i]) {
      d[i] = 1;
      for(register int j = (i << 1); j <= lim; j += i)
        ++ d[j];

      ll pp = 1LL * i * i;
      for(register ll j = pp; j <= lim; j += pp)
        b[j] = true;
    }
  }

  /// PIE
  for(register int i = 2; i <= lim; ++ i)
    if(!b[i])
      ans += 1LL * (d[i] & 1 ? 1 : -1) * (N / i) * (M / i);
  printf("%lld\n", 1LL * N * M - ans);
  return 0;
}