ABC 170 D - Not Divisible

問題

長さ $n$ の数列 $A$ が与えられる。任意の $j \neq i$ に対して $A _i$ が $A _ j$ で割り切れないような $i$ の個数を求めよ。（$n \leq 2 \times 10 ^ 5$, $A _ i \leq 10 ^ 6$）

atcoder.jp

解説

$A _ i$ 以外で $A$ の中に $A _ i$ の約数がないような $i$ の個数を求めればよい。各 $a$ について自分以外に約数か存在するどうかのフラグを用意する。$a$ が $A$ に複数存在するなら $1$ とし、さらに $2a,3a,\ldots$ のフラグも $1$ にする。最後にフラグが $0$ となっている $a$ の個数を数えればよい。

実装

n = int(input())
*A, = map(int, input().split())
maxA = max(A)
C = {a: 0 for a in A}
for a in A:
    C[a] += 1
D = {a: 0 for a in A}
for a in A:
    if C[a] > 1:
        D[a] = 1
    for b in range(2 * a, maxA + 1, a):
        D[b] = 1
print(sum([D[a] == 0 for a in A]))

atcoder.jp