この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。
68. NTL_1_A – 素因数分解
AtCoder 版！マスター・オブ・整数 (素因数分解編) の「4. 素因数分解」に本問題の解説があります。その解説の通りに実装すれば求解できます。
計算量は O(\sqrt{n}) = 10^5 程度です。
69. AtCoder Beginner Contest 084 D – 2017-like Number
ある奇数 N に対し、以下の記事の素数判定法を N と (N + 1) \div 2 に対して用いると計算量 O(\sqrt{N}) で N が 2017に似た数 であるか判定できます。
- レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 の「高速な素数判定法」
- AtCoder 版！マスター・オブ・整数 (素因数分解編) の「2. 素数判定」
クエリが来るたびに区間 [l_i, r_i] の整数が 2017に似た数 であるかを判定する場合、計算量は \Omega(\sqrt{N} \sum_{i = 1}^Q (r_i – l_i + 1)) = 10^{13} 程度になり、実行時間制限に違反しそうです。
判定を行う回数を減らすため、l_i の下限である 1 から r_i の上限である 10^5 までの奇数に対し、2017に似た数 であるかをあらかじめ判定しておきます。これは 10^5 \div 2 \times 2 \times 10^{5/2} = 10^{7.5} 程度の計算量でできます。
2017に似た数 の情報を持っていても、クエリが来るたびに区間 [l_i, r_i] の整数を確認する場合、計算量は \Omega(\sum_{i = 1}^Q (r_i – l_i + 1)) = 10^{10} 程度になります。まだ実行時間制限に違反しそうです。この計算量の削減には累積和を使います。累積和については下記の記事が参考になります。
この問題での累積和の使い方は上記の記事の「問題 2： AtCoder ABC 084 D – 2017-like Number」に書いてあります。この方法を用いると 10^5 程度の計算量の前準備で各クエリに対して O(1) の計算量で解答できるため、10^5 + Q \times O(1) = 10^6 程度の計算量で Q 個のクエリを処理できます。
全体の計算量は 10^{7.5} + 10^6 \leq 10^8 程度となり、実行時間制限を満たして解答できます。
注意 以下では レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 の「2-1. 「水色コーダー」で要求される 4 つのこと」の「条件 2」には記載のないアルゴリズム「エラトステネスのふるい」を用います。
累積和を何も考えずに書けるようにする！ の本問題の解説にある通り、エラトステネスのふるいというアルゴリズムを用いても素数を列挙できます。計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 「例 14: エラトステネスのふるい O(n loglogn)」によると整数 N までの素数の列挙の計算量は O(N \log \log N) だそうです。
エラトステネスのふるいを用いた場合、全体の計算量は 10^6 + 10^6 \leq 10^7 程度になります。ただ、この問題の場合、10^5 までの素数の列挙よりその他の部分の計算の方が重いようで、私の解答例ではあまり恩恵は得られませんでした。
下記の解答例を見る限り、この問題の規模だと 競技プログラミングにおけるC++の定数倍高速化テク に記載のテクニックで入出力の設定を変更する方がより効果的な高速化だと考えられそうです。
