AtCoder Beginner Contest 170 D - Not Divisible

考え方

エラトステネスの篩が思い浮かべばほぼ勝ち。こういうときはAiから考えがちではあるが、Ajから考えるとよい。

• (1 <= j <= N)について、Ajを除くAjの倍数はダメ
• それぞれの数について、2個以上含まれている場合はダメ

これらを、与えられた数列の各要素においてチェックする 。

実装

制約を見るとAi <= 10⁶なため、予めBooleanArray(A_max)を用意してチェックを行うことができる。また、同じ数を2回チェックしたことを検出するためにもう一つBooleanArrayを用意する。

val dp = BooleanArray(max + 1) { true } //1つ目の条件用配列
val searched = BooleanArray(max + 1) { false } //2つ目の条件用配列

各要素Aiのチェック時に、

• その数を除いた倍数をA_maxを超えるまでdpをfalseに
• 一回目のチェックでsearchedをtrueに、2回目以降にチェックした場合はその数のdpをfalseに

という感じ。

 A.forEach { it ->
    val a = it
    if (searched[a]) {
        dp[a] = false
        return@forEach
    }
    searched[a] = true
    var i = a * 2
    while (i <= max) {
        dp[i] = false
        i += a
    }
}

最後にdpがtrueの要素を数える

A.filter { a ->
    dp[a]
}.size.let {
    println(it)
}

ソースコード