Cod sursa(job #1529183)

Utilizator tudorcomanTudor Coman tudorcoman Data 20 noiembrie 2015 16:27:39
Problema Mins Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 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 = 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", N * M - ans);
  return 0;
}