解法. 二部グラフの最大マッチング
部グラフをそれぞれ青いカードと赤いカードの集合として,互いに素でない青いカードと赤いカードの間に辺を張ってできる2部グラフ上での最大マッチングが答えとなる.マッチングとは辺部分集合でどの2辺も端点を共有しないものである.2部グラフの最大マッチングは最大流問題に帰着して解くことができる.
計算時間:
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int src, dst;
Edge(int f, int t) :
src(f), dst(t) {}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;
bool Augment(const Graph& g, int u,
vector<int>& matchTo, vector<bool>& visited) {
if (u < 0) return true;
for (auto e : g[u])
if (!visited[e.dst]) {
visited[e.dst] = true;
if (Augment(g, matchTo[e.dst], matchTo, visited)) {
matchTo[e.src] = e.dst;
matchTo[e.dst] = e.src;
return true;
}
}
return false;
}
int BipartiteMaximumMatching(const Graph& g, int L) {
const int n = g.size();
Edges matching;
vector<int> matchTo(n, -1);
int match = 0;
for (int u = 0; u < L; ++u) {
vector<bool> visited(n);
if (Augment(g, u, matchTo, visited))
++match;
}
for (int u = 0; u < L; ++u)
if (matchTo[u] >= 0)
matching.emplace_back(Edge(u, matchTo[u]));
return match;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int m, n;
while (cin >> m >> n, m) {
vector<int> b(m), r(n);
for (auto &x : b) cin >> x;
for (auto &x : r) cin >> x;
Graph g(m + n);
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (__gcd(b[i], r[j]) != 1)
g[i].emplace_back(Edge(i, j + m));
cout << BipartiteMaximumMatching(g, m) << '\n';
}
return 0;
}
まとめ
C++17からSTLにgcdが入る[2] みたいで嬉しい.