競プロチャレンジ供養会場: AtCoder Regular Contest 124 C - LCM of GCDs

コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 1495 (記事作成時点)

供養

解法

• $a_{1}, b_{1}$ が入った集合の約数をそれぞれ $x, y$ と決め打った時に、それらを約数とするような集合を作れるかは $O(N)$ で計算できる
  • 各 $i$ について、$x$ が $a_{i}$ の約数かつ $y$ が $b_{i}$ の約数であるか、$x$ が $b_{i}$ の約数かつ $y$ が $a_{i}$ の約数であるかを調べればよい
• 集合を作れるような $x, y$ の最小公倍数の最大値を答えとすればよい
• $x, y$ はそれぞれ $a_{1}, b_{1}$ の約数を全列挙して調査しても十分間に合う

実装

計算量は $a_{1}, b_{1}$ の約数の数をそれぞれ $d(a_{1}), d(b_{1})$ として $O(d(a_{1})d(b_{1})N)$

公式解説

躓いた点

• 約数の全列挙を思いつかなかった