Cod sursa(job #2845278)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 7 februarie 2022 18:05:16
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("mins.in");
ofstream fout("mins.out");

const int kN = 1e6;
short cnt[1 + kN];

void testCase() {
  int c, d;
  fin >> c >> d;
  c -= 1, d -= 1;
  if (d < c) {
    swap(c, d);
  }
  int64_t ans = (int64_t)c * d;
  for (int i = 2; i <= c; ++i) {
    if (cnt[i] == 0) {
      for (int j = i; j <= c; j += i) {
        if (cnt[j] != -1) {
          cnt[j] += 1;
        }
      }
      if ((int64_t)i * i <= c) {
        for (int j = i * i; j <= c; j += i * i) {
          cnt[j] = -1;
        }
      }
    }
    if (cnt[i] != -1) {
      if (cnt[i] % 2 == 1) {
        ans -= (int64_t)(c / i) * (d / i);
      } else {
        ans += (int64_t)(c / i) * (d / i);
      }
    }
  }
  fout << ans << '\n';
}

int main() {
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  fin.close();
  fout.close();
  return 0;
}