Cod sursa(job #2242009)

Utilizator lucametehauDart Monkey lucametehau Data 17 septembrie 2018 16:14:03
Problema Mins Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <fstream>
#include <bitset>

using namespace std;

ifstream cin ("mins.in");
ofstream cout ("mins.out");

const int NMAX = 1e6;

int n, m, mn;
long long sol;

int dv[1 + NMAX];
bitset <1 + NMAX> viz;

int main() {
  cin >> n >> m;
  n--; m--;
  mn = min(n, m);
  for(int i = 2; i <= mn; i++) {
    if(dv[i] == 0) {
      for(int j = i; j <= mn; j += i)
        dv[j]++;
      if(mn / i < i)
        continue;
      for(int j = i * i; j <= mn; j += i * i)
        viz[j] = 1;
    }
  }
  sol = 1LL * n * m;
  for(int i = 2; i <= mn; i++) {
    if(viz[i])
      continue;
    if(dv[i] % 2)
      sol -= (n / i) * (m / i);
    else
      sol += (n / i) * (m / i);
  }
  cout << sol;
  return 0;
}