https://atcoder.jp/contests/abc084/submissions/15381403
- 素数テーブルと2017に似た数字の前処理をしておくことで各クエリを
にする
制約から各クエリを以下で処理する必要がある。範囲クエリを
で処理する方法として累積和を使いたくなる。素数テーブルを用意しておけば予め2017に似た数を列挙するのは線形時間で処理できる。あとは2017に似た数を累積和にしておくことで、全体計算量が
になる。
https://atcoder.jp/contests/abc084/submissions/15381403
制約から各クエリを以下で処理する必要がある。範囲クエリを
で処理する方法として累積和を使いたくなる。素数テーブルを用意しておけば予め2017に似た数を列挙するのは線形時間で処理できる。あとは2017に似た数を累積和にしておくことで、全体計算量が
になる。