ARC114所感

atcoder.jp

どうも、０完太陽と申します。

A

考え得る素数の部分集合を全列挙し、それらの積Yについて、条件を満たすか考えればよいです。

 O(2^15*(15+NlogN))といったところでしょうか

※2^15通りの部分集合についてまず積を求め(15)、N個の数と互いに素であるか判定(logN)

最悪計算量は12076757≒1.2*10^7<10^8なので、1secにも余裕で間に合うという訳です

こういった逆の発想ができるようになりたいです。