Edit

【pythonでABC170を解説】D - Not Divisible

問題概要

問題ページ

問題文

長さ \(N\) の数列 \(A\) が与えられます。

次の性質を満たす整数 \(i\) \(\left(1 \leq i \leq N \right)\) の数を答えてください。

  • \(i \neq j \) である任意の整数 \(j\) \(\left(1 \leq j \leq N\right)\) について \(A_i\) は \(A_j\) で割り切れない

制約

  • 入力は全て整数
  • \(1 \leq N \leq 2 \times 10^5\)
  • \(1 \leq A_i \leq 10^6\)

問題の考察

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = sorted(list(map(int, input().rstrip('\n').split())))
    ca = collections.Counter(a)
    ls = [True] * (a[-1] + 1)
    for v in a:
        if ls[v]:
            if ca[v] > 1:
                ls[v] = False
            for i in range(v * 2, a[-1] + 1, v):
                ls[i] = False
    cnt = 0
    for v in a:
        cnt += 1 if ls[v] else 0
    print(cnt)


if __name__ == '__main__':
    solve()

プログラミング

-Edit
-