JAG Practice Contest for ACM-ICPC Asia Regional 2017 C- Prime-Factor Prime

• 問題
• AC

第一感で時間が厳しそうと思ったけど、ぜんぜん厳しくなかった。相変わらず計算量は難しい。素数の逆数和や素因数の個数の和がなかなか増加しないところがポイントか。

以下、主に計算量について。$\Delta := r - l$とする。

1. 前処理で$\sqrt{r}$までの素数を列挙する。エラトステネスの篩で${\mathcal O}(\sqrt{r}\log\log r)$。
2. 次に$\{l, l+1, ..., r\}$を$\sqrt{r}$までの素数でふるう。各整数を素数で割れるだけ割りながら、素因数の数を数えていく。
   • ループの回数はエラトステネスの篩と同様な見積もりが可能で、$\sum_{p\le \sqrt{r}, \: pは素数} \Delta/p = {\mathcal O}(\Delta \log\log r)$となる。
   • ただし、素因数を数えるために各整数を素数で割っていく操作を${\mathcal O}(1)$とはみなせないのが問題……だが、Prime omega functionを見る限り、$\{l, l+1, ..., r\}$内の整数の素因数の数を合計すると${\mathcal O}(\Delta \log\log r)$でよさそうなので、結局計算量は変わらないはず。（自信なし）
3. $\{l, l+1, ..., r\}$内の整数の素因数の数をすべて数え終わったら、それが素数であるものを数えていく。前処理で作った素数テーブルを使えばよい。${\mathcal O}(\Delta)$。

まとめると、おそらく${\mathcal O}((\sqrt{r}+\Delta) \log\log r$)になるのだが、自信がない。$n \in \{l, l+1, ..., r\}$の素因数の数は高々$\log_2 r$なので、${\mathcal O}(\sqrt{r}\log\log r + \Delta \log r$)なのは間違いない。