ABC084 D 2017-like-number
ABC084 D 2017-like-number writeup
D
https://beta.atcoder.jp/contests/abc084/submissions/2379051
問題概要
Nが素数 && (N+1)/2も素数 を満たす奇数Nを2017 like numberとするとき、Q個以下のクエリ(l,r)について、[l,r]に含まれる2017 like numberの数を答える問題。
制約
l,rは奇数
入力はすべて整数
取った方針
クエリがQ個(最大1e+5個)降ってくるのでクエリに対してO(1)で答える必要がある。
a[i]にiまでの2017-like-numberの個数の和を記録しておいて、(l,r)に対してa[r] - a[l-1]を計算すればクエリに対してO(1)で答えることができる。この手法を累積和とか言ったりする。
エラトステネスの篩はO(NloglogN)(らしい)かつ、累積和の計算はO(r)で計算できるので間に合う。
正しい方針
取った方針の通り。
得られた知見
・エラトステネスの篩を4年ぶりくらいに書いた
・累積和のつかいかた
・(一般化)高速に区間に含まれる何かの数を数えたい場合、などは累積和の活用ができないか考える。
解くのに必要な要素
・素数判定(エラトステネスの篩)
・累積和
周辺調査によって得られた知見
特になし