AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

ABC170 D - Not Divisible

問題原文

atcoder.jp

解法

エラトステネスの篩っぽく、「 i を割るような  A_j が何個あるか」を数える。
これは調和級数っぽい形になるので、実は  O(NlogN) ぐらいでできる。

ただし重複する数をそのまま処理すると、2 2 2 2 .... 2 2 2 をはじめとするパターンでTLEしてしまうので注意。

実装

ほんとは  2a から回すべきだった。
それなら boolで判定できるので。

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)

A = set(A)
MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
    for i in range(a, MAX_A + 1, a):
        X[i] += 1

ans = len([a for a in A if (X[a] == 1) and (C[a] == 1)])
print(ans)

感想

篩の考え方しょっちゅうでるなぁ。