D - Not Divisible

[hxrxchang]

https://atcoder.jp/contests/abc170/tasks/abc170_d

問題概要

長さNの数列Aがある。 以下の性質を満たす整数 i (1 <= j <= N) の個数を求めよ

• i != j (1 <= j <= N) である任意の整数 jについて、A[i] % A[j] != 0

制約

• 1 <= N <= 2 * 10 ** 5
• 1 <= A[i] <= 10 ** 6

解き方

ダメな例は、a[i]の約数をあらかじめ列挙して、a[i]の他の要素が約数に含まれているかチェックする方法。 a[i]は10 ** 6なので、約数列挙にはそこまでコストがかからないが、a[i] の他の要素がa[i]の約数に含まれるかどうかを見るのに二重ループになってしまう。

各a[i]の出現回数を記録する。 1~max(a)まで、その値が出現したら、

• 複数回出現しているということは、その要素は割り切れる。
• 1回しか出現していない場合は、その倍数となる要素は割り切れる。これをエラトステネスの篩の要領で切り落としていく。

という考えで、↑に当てはまる要素の出現回数を0に上書きしていく。 エラトステネスの篩の計算量は、調和級数(数が大きくなると、その倍数の個数は比例して少なくなっていく)なので、計算量は maxA * log(maxA) (maxAは10 ** 6)で収まる。

func solve() {
    getInt()
    a := getInts()
    maxA := max(a...)

    cntA := make([]int, maxA + 1)
    for _, v := range a {
        cntA[v]++
    }

    for i := 1; i <= maxA; i++ {
        if cntA[i] == 0 {
            continue
        }

        // 同じ要素が複数あったら割り切れるので0にする
        if cntA[i] > 1 {
            cntA[i] = 0
        }

        // エラトステネスの篩と同じ要領でiの倍数を0にする
        // 自分自身は残すようにstartをi*2にする
        for j := i * 2; j <= maxA; j += i {
            cntA[j] = 0
        }
    }

    ans := 0
    for _, v := range cntA {
        ans += v
    }

    fmt.Println(ans)
}

https://atcoder.jp/contests/abc170/submissions/54203918