ABC170

NISHIO Hirokazu [Translate]

ABC170
atcoder 3問解いて、Dのタイムアウトを解決する方法がさっぱり思いつかないのでEを見て、 Eの要求を満たすデータ構造が思いつかないので第三回 アルゴリズム実技検定の解説を読んでた(問題Kの解法が参考にならないかと思ったけど、僕のやった手法をもう少し簡素にしたものだったので参考にならなかった)


解説PDFに書かれてたけどCは易しい問題とのことで、僕も特に書くことはない。あんまりレートも上がらない。

問題D
20万個の数値があって「自分以外のすべてで割り切れない数値」がいくつあるか答える問題。
素直に割り算すると20万の二乗のオーダーでTLE。
いくつかの細かい枝切りは思いつくものの抜本的にオーダーを変える方法を思いつかなかった。

解答編。エラトステネスのふるいを使う。
値の範囲が10^6以下なので最大でそのサイズのテーブルがあれば良い。
最大値までのテーブルを作り、大きい順に
自分の場所に1を書く
自分の倍数のところに0を書く
をやる。もしも自分以外の数で割り切れるなら、自分より小さい数が「倍数に0を書く」をやった時に上書きされるはずである。
最後にテーブルに書かれた数を全部足せば、条件を満たす数の個数がわかる。

ただし罠があって、同じ数が複数回出てくる時にはこの方法ではその数に1が立ってしまう。なので2回目以降なら0を書く必要がある。

pythonN = int(input())
AS = [int(x) for x in input().split()]

AS.sort(reverse=True)
MAX_AS = AS[0]
table = [0] * (MAX_AS + 1)  # 1..max(AS)

alreadyVisited = {}
for i in range(N):
    x = dx = AS[i]
    if alreadyVisited.get(x, False):
        table[x] = 0
        continue
    alreadyVisited[x] = True

    table[x] = 1
    while True:
        x += dx
        if x > MAX_AS:
            break
        table[x] = 0

print(sum(table))

ABC170_E