Cod sursa(job #2307481)

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

using namespace std;

const int MAXN = 1e6;

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

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