AT_arc124_c [ARC124C] LCM of GCDs

[problemUrl]: https://atcoder.jp/contests/arc124/tasks/arc124_c 赤い袋と青い袋と $ N $ 個のカードパックがあります。はじめどちらの袋も空です。 それぞれのカードパックには整数が書かれた $ 2 $ 枚のカードが封入されており、$ i $ 番目のカードパックに入っているカードにはそれぞれ $ a_i,b_i $ が書かれていることがわかっています。 それぞれのカードパックについて、一方のカードを赤い袋に、他方のカードを青い袋に入れます。 カードを袋に入れ終えたのち、赤い袋に入ったカードに書かれた整数全体の最大公約数を $ X $ とします。 同様に、青い袋に入ったカードに書かれた整数全体の最大公約数を $ Y $ とします。 $ X $ と $ Y $ の最小公倍数の値が得点となります。 得点としてありうる値の最大値を求めてください。

N/A

N/A

### 制約 - 与えられる入力は全て整数 - $ 1\ \leq\ N\ \leq\ 50 $ - $ 1\ \leq\ a_i,\ b_i\ \leq\ 10^9 $ ### Sample Explanation 1 \- $ 2 $ が書かれたカードを赤い袋に入れ、$ 15 $ が書かれたカードを青い袋に入れ、$ 6 $ が書かれたカードを赤い袋に入れ、$ 10 $ が書かれたカードを青い袋に入れるのが最適な入れ方の $ 1 $ つです。 - このとき、赤い袋に入ったカードに書かれた整数全体の最大公約数は $ 2 $、青い袋に入ったカードに書かれた整数全体の最大公約数は $ 5 $ です。 - このときの得点は $ 10 $ です。