ABC215 D Coprime 2
条件を言い換えると, $ lcm(A_1, A_2, A_3, ..., A_N) = Lとおいて, $ gcd(L, k) = 1となるような$ 1以上$ M以下の整数$ kを全て求めればよいことになる. $ Lをそのまま求めるととても巨大になってしまう場合があるので, $ Lを素因数分解した形で持つことを考える. 今回は互いに素かどうかのみ考えればよいので, どの素因数が登場するかという情報のみ考えればよい. これは, $ A_1, A_2, A_3, ..., A_Nのそれぞれを素因数分解することで求められる. あとは$ kを全探索し, 素因数分解して$ kの素因数に$ Lと重複がないか調べることにより, この問題を解くことができる.
計算量は高速な素因数分解(エラトステネスの篩による素数前計算)とmapを利用すると, $ max(A_1, A_2, A_3, ..., A_N) = mとして$ O(N \log m + M \log M \log m)となる.