D - Not Divisible(Python)

はじめに

リアルタイムで解いてない。3完。最近ABCでは4完続いてたので悔しい。 公式の解説を参考に分からなかったところや覚えておきたいところをメモしていく。

D Not Divisible

• 先に約数をカウントする配列divを作っておく。

• numが入力されたら、上記配列のインデックスdiv[num],div[num x 2],div[num x 3],......div[1000000]に+1をする、というような処理を入力された分だけ行う。ただしすでにdiv[num]に1以上の数字が入ってる場合は、すでにdiv[num x 2]以降は更新されているので、div[num] += 1だけをやる。(例えば、1が入力されたときM回ループする処理を何度もされるなど、入力によっては間に合わない可能性があるので、そもそもdiv[num]に1以上の数字が入っている場合は、 div[num] += 1だけをしてdiv[num+num]....には+1の処理をしないほうがよい。)

• 上記計算量は M = 10 ** 6としたとき下記になり、間に合う。logMは大体20くらい。

• 最後は入力された配列Aの中の値aをインデックスにとるdiv[a]をチェックして、これが1ならans+=1を、それ以外なら何もしない。

div = [0] * 1000005

N = int(input())
A = list(map(int, input().split()))

for num in A:
    if div[num] == 0:
        for i in range(num, 1000004, num):
            div[i] += 1
    elif div[num] != 0:
        div[num] += 1        

ans = 0

for num in A:
    if div[num] == 1:
        ans += 1

print(ans)