[AtCoder] ABC 177 E – Coprime

問題

方針

\( N \) 個の整数が ‘pairwise coprime’ であれば ‘setwise coprime’ なので、’pairwise coprime’かどうかを先に調べます。\( N \) 個の整数において、\( i \ ( 2 \leq i \leq 10^6)\) の倍数の数が \( 1 \) 以下であれば ‘pairwise coprime’ であると言えます。次に、\( i \) の倍数が \( N \) 個あるとき、’not coprime’となります。そうでなければ、’setwise coprime’ となります。

したがって、\( i \) の倍数の個数を \( B_i \) として、この配列を全探索します。

コード