Cod sursa(job #1529180)

Utilizator tudorcomanTudor Coman tudorcoman Data 20 noiembrie 2015 16:23:42
Problema Mins Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb

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

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

inline int semn(int i) {
  return d[i] & 1 ? 1 : -1;
}

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

  /// i = 2
  d[2] = 1;
  for(register ll 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 ll 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 ll i = 2; i <= lim; ++ i)
    if(!b[i])
      ans += 1LL * semn(i) * ((N - 1) / i) * ((M - 1) / i);
  printf("%lld\n", (N - 1) * (M - 1) - ans);
  return 0;
}