ICPC国内予選2009 E問題 : カードゲーム

問題. カードゲーム

1より大きい整数が1つ書かれた  m 枚の青いカードと  n 枚の赤いカードが場にある.青いカードと赤いカードのペアが1より大きい共通の約数があるとき場からペアを取り除くことができる.最大何組のカードを場から取り除けるかを求めよ.

制約 1 \le m \le 500,  1 \le n \le 500

解法. 二部グラフの最大マッチング

部グラフをそれぞれ青いカードと赤いカードの集合として,互いに素でない青いカードと赤いカードの間に辺を張ってできる2部グラフ上での最大マッチングが答えとなる.マッチングとは辺部分集合でどの2辺も端点を共有しないものである.2部グラフの最大マッチングは最大流問題に帰着して解くことができる.

計算時間 O((n + m) \times nm)

まとめ

C++17からSTLにgcdが入る[2] みたいで嬉しい.