7K12 blog

猫でも分かるアルゴリズム解説

ABC084 D - 2017-like Number

f:id:tkr987:20200724004907p:plain

https://atcoder.jp/contests/abc084/submissions/15381403

  • 素数テーブルと2017に似た数字の前処理をしておくことで各クエリを O(1)にする

f:id:tkr987:20200724014207p:plain

制約から各クエリを O(\log N)以下で処理する必要がある。範囲クエリを O(1)で処理する方法として累積和を使いたくなる。素数テーブルを用意しておけば予め2017に似た数を列挙するのは線形時間で処理できる。あとは2017に似た数を累積和にしておくことで、全体計算量が O(Q)になる。