Cod sursa(job #2307480)

Utilizator cella.florescuCella Florescu cella.florescu Data 24 decembrie 2018 18:02:05
Problema Mins Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6;

int coef[MAXN + 1], seen[MAXN + 1];

int main()
{
    for (int i = 0; i <= MAXN; ++i)
      coef[i] = 1;
    for (int i = 2; i <= MAXN; ++i)
      if (seen[i] == 0)
        for (int j = i; j <= MAXN; j += i) {
          coef[j] *= -1;
          seen[j] = 1;
        }
    for (int i = 2; i * i <= MAXN; ++i)
      for (int j = 1; i * i * j <= MAXN; ++j)
         coef[i * i * j] = 0;
    int n, m;
    ifstream fin("mins.in");
    fin >> n >> m;
    fin.close();
    long long ans = 1LL * (--n) * (--m);
    for (int i = 2; i <= MAXN; ++i)
      ans += 1LL * coef[i] * (n / i) * (m / i);
    ofstream fout("mins.out");
    fout << ans << '\n';
    fout.close();
    return 0;
}