ABC170 D - Not Divisible
問題原文
解法
エラトステネスの篩っぽく、「 を割るような が何個あるか」を数える。
これは調和級数っぽい形になるので、実は ぐらいでできる。
ただし重複する数をそのまま処理すると、2 2 2 2 .... 2 2 2
をはじめとするパターンでTLEしてしまうので注意。
実装
ほんとは から回すべきだった。
それなら 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)
感想
篩の考え方しょっちゅうでるなぁ。