[AtCoder] ABC 170 D – Not Divisible

問題

方針

数列に \( 1 \) が含まれるとき、\( 1 \) の個数が \( 1 \) ならば、答えは \( 1 \) であり、複数あれば答えは \( 0 \) となります。次に、数列に \( 1 \) が含まれない場合を考えます。同じ値の要素は互いに割り切れるので、数列のセット \( s \) を考えます。ここで、\( s \) の要素の倍数を列挙します。倍数は \( 10^6 \) 以下のものを考えます。この計算量は、

\[ 10^6(1 + \dfrac{1}{2} + \cdots + \dfrac{1}{N})\]

以下なので、行うことができます。したがって、\( A_i \) が \( s \) の要素の倍数に含まれるかどうかを調べればよいです。

コード