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

問題概要

問題ページ

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()