ymduu+2

初心を忘れないのでツンデレとPSPが今でも好き、技術メモとか制作物とかそういうの

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の数を答える問題。

制約

 1 \leq Q \leq 10^5
 1 \leq l \leq r \leq 10^5
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年ぶりくらいに書いた
・累積和のつかいかた
・(一般化)高速に区間に含まれる何かの数を数えたい場合、などは累積和の活用ができないか考える。

解くのに必要な要素

素数判定(エラトステネスの篩)
・累積和

周辺調査によって得られた知見

特になし