ARC114 A Not coprime
条件を満たす
$ Y
のうち最小のものとして考えられるのは相異なる素数をいくつか掛けたものである. ここで,
$ X_i \leq 50
と非常に小さいことに注目する.
$ 50
以下の素数の個数は高々
$ 15
個なので, どの素数を選ぶかbit全探索し, 条件を満たすもののうち最小のものを求めればよい. 計算量は
$ O(N2^{\pi(max\{X_i\})} \log max\{X_i\})
となって十分高速である.
実装例:
https://atcoder.jp/contests/arc114/submissions/20958473