Cod sursa(job #2241671)

Utilizator PetyAlexandru Peticaru Pety Data 16 septembrie 2018 17:57:22
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <bits/stdc++.h>

using namespace std;

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

int c, d, nr[1000002], pp[1000002];
long long sol;

void bruv () {
  for (int i = 2; i <= c; i++) {
    if (!nr[i]) {
      for (int j = i; j <= c; j += i)
        nr[j]++;
      for (int j = i * i; j <= c; j += i * i)
        pp[j] = 1;
    }
  }
}

int main()
{
  cin >> c >> d;
  c--;
  d--;
  if (c > d)
    swap(c, d);
  bruv();
  sol = 1LL * c * d;
  for (int i = 2; i <= c; i++) {
    if (pp[i])
      continue;
    if (nr[i] % 2)
      sol -= 1ll * (c / i) * (d / i);
    else
      sol += 1ll * (c / i) * (d / i);
  }
  cout << sol;
  return 0;
}