Cod sursa(job #3029988)

Utilizator IanisBelu Ianis Ianis Data 17 martie 2023 12:45:31
Problema Mins Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#include <deque>
#include <cmath>

using namespace std;

#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("mins.in");
ofstream fout("mins.out");
#define endl '\n'
#endif

const int NMAX = 5005;

int n, m;
int ans;
int last[NMAX];
vector<int> p;
vector<int> fact[NMAX];

void desc(int x) {
    if (x == 1) return;
    int n = x;
    int i = 0;
    while (p[i] * p[i] <= n) {
        if (n % p[i] == 0) {
            fact[x].push_back(p[i]);
            while (n % p[i] == 0)
                n /= p[i];
        }
        i++;
    }
    if (n == 1) return;
    if (fact[x].empty() || fact[x].back() != n) fact[x].push_back(n);
}

void precalc() {
    last[1] = 1;
    p.reserve(670);
    for (int i = 2; i < NMAX; i++) {
        if (last[i] == 0) {
            last[i] = i;
            p.push_back(i);
        }
        for (int j = 0; j < p.size() && i * p[j] < NMAX; j++) {
            last[i * p[j]] = p[j];
            if (i % p[j] == 0) break;
        }
    }
    for (int i = 1; i < NMAX; i++) {
        desc(i);
    }
}

bool prime(int x, int y) {
    int i = 0, j = 0;
    while (i < fact[x].size() && j < fact[y].size()) {
        if (fact[x][i] == fact[y][j]) return false;
        if (fact[x][i] < fact[y][j]) i++;
        else j++;
    }
    return true;
}

int main() {
    fin >> n >> m;
    precalc();
    for (int x = 1; x < n; x++) {
        for (int y = 1; y < m; y++) {
            ans += prime(x, y);
        }
    }
    fout << ans;
    return 0;
}