足跡-sokuseki-

りかの日進月歩の記録

ABC084 D 2017-like Number

競技プログラミング AtCoder

400点以上の問題は積極的にブログに書こうと思います。

D - 2017-like Number

問題概要

「 $N$ も $\frac{N+1}{2}$ も素数」を満たす奇数 $N$ を2017に似た数と定義する。
$Q$ 個のクエリが与えられるので、それぞれのクエリに対して、 $l_i \le x \le r_i$ かつ2017に似た数となる奇数 $x$ の個数を答えよ。

制約
$1 \le Q \le 10^5$
$1 \le l_i \le r_i \le 10^5$

解法

方針は以下の通り。

$N$ のとりうる上限( $10^5$ )まで素数判定をする(試し割りだと間に合わないのでエラトステネスの篩を使う)
$N$ のとりうる上限( $10^5$ )まで2017に似た数判定をする
累積和を使って、「N以下の2017に似た数の個数」をすべて*1の $N$ について求める
各クエリ $l_i, r_i$ に対して、 $r_i$ 以下の2017に似た数の個数から $l_i$ 以下の2017に似た数の個数を引いたものを出力する

Submission #1961699 - AtCoder Beginner Contest 084

感想

そすーそすー

*1:本当は奇数だけで良いが、場合分けが面倒なので