lessons/参考实现/07-二分图/CodeForces-498C.cpp

#include <algorithm>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

struct Dinic {
    struct Edge { int to, reverse, capacity; };
    vector<vector<Edge>> g;
    vector<int> level, cursor;
    explicit Dinic(int n) : g(n), level(n), cursor(n) {}
    void add_edge(int u, int v, int capacity) {
        Edge a{v, static_cast<int>(g[v].size()), capacity};
        Edge b{u, static_cast<int>(g[u].size()), 0};
        g[u].push_back(a); g[v].push_back(b);
    }
    bool bfs(int source, int sink) {
        fill(level.begin(), level.end(), -1); queue<int> q;
        level[source] = 0; q.push(source);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (const Edge &e : g[u]) if (e.capacity > 0 && level[e.to] == -1) {
                level[e.to] = level[u] + 1; q.push(e.to);
            }
        }
        return level[sink] != -1;
    }
    int dfs(int u, int sink, int pushed) {
        if (u == sink) return pushed;
        for (int &i = cursor[u]; i < static_cast<int>(g[u].size()); ++i) {
            Edge &e = g[u][i];
            if (e.capacity > 0 && level[e.to] == level[u] + 1) {
                int flow = dfs(e.to, sink, min(pushed, e.capacity));
                if (flow) {
                    e.capacity -= flow; g[e.to][e.reverse].capacity += flow; return flow;
                }
            }
        }
        return 0;
    }
    int max_flow(int source, int sink) {
        int answer = 0, flow;
        while (bfs(source, sink)) {
            fill(cursor.begin(), cursor.end(), 0);
            while ((flow = dfs(source, sink, numeric_limits<int>::max() / 4)) > 0) answer += flow;
        }
        return answer;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector<int> a(n), original(n), primes;
    for (int &x : a) cin >> x;
    original = a;
    for (int x : a) {
        for (int p = 2; 1LL * p * p <= x; ++p) if (x % p == 0) {
            primes.push_back(p); while (x % p == 0) x /= p;
        }
        if (x > 1) primes.push_back(x);
    }
    sort(primes.begin(), primes.end()); primes.erase(unique(primes.begin(), primes.end()), primes.end());
    vector<pair<int, int>> pairs(m);
    for (auto &[u, v] : pairs) { cin >> u >> v; --u; --v; if (u % 2 == 1) swap(u, v); }

    int answer = 0, source = n, sink = n + 1;
    for (int prime : primes) {
        Dinic flow(n + 2); vector<int> exponent(n);
        for (int i = 0; i < n; ++i) {
            int x = original[i];
            while (x % prime == 0) ++exponent[i], x /= prime;
            if (i % 2 == 0) flow.add_edge(source, i, exponent[i]);
            else flow.add_edge(i, sink, exponent[i]);
        }
        for (auto [u, v] : pairs) flow.add_edge(u, v, 1'000'000);
        answer += flow.max_flow(source, sink);
    }
    cout << answer << '\n';
}