AtCoder Beginner Contest 170 [ D - Not Divisible ] をPythonで解く(400点、🟩緑diff)
問題
解法
数列Aの中のAiの倍数を配列fをつくって、あらかじめカウントしておく。
f[i]はIの約数の数が入る。
これができてしまえば、Aiの数値の約数はf[Ai]を参照すればわかる。
f[Ai]が1ならば、Aiの約数は自分自身しかないので、数列Aの中にAiが割れる約数は存在しないことがわかる。
計算量はAiの最大値106から、O(106 x log106)