今日の精進 ABC170D

一昨日のABCで3完でレートを冷やしてしまったのでその反省です。

D - Not Divisible

配点 : 400点

問題文

長さ の数式 が与えられます。 次の性質を満たす整数 の数を答えてください。

• である任意の整数 について は で割り切れない

制約

• 入力は全て整数
• 
• 
• 

コンテスト中の解法

• の数についてそれぞれカウントし、重複がある場合既出扱いにする
• を昇順にソート
• 各に対して約数を列挙し、その約数が既出かどうかを判定する
  • 既出である場合、その数は割り切れるためカウントしない
  • 既出でない場合、カウントを行なう

約数列挙にかかるので全体ででC++なら行けるかなと思った。 結果、WA取れず。

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

想定解

小さい方からエラストテネスの篩と同じように処理をして埋めていくことで解ける。 埋める数は徐々に減り、調和級数で表せるので全体で[tex: O(A{max}logA{max}+NlogN)]になる。 これならpythonでも問題なさそう。

import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip()

MAX = 1000001
dp = [True for _ in range(MAX)]
n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
a = sorted(list(set(a)))
ans = 0
for v in a:
   if cnt[v] <= 1 and dp[v]:
      ans += 1
   m = v
   while m < MAX:
      dp[m] = False
      m += v
print(ans)

Submission #14403324 - AtCoder Beginner Contest 170