No.1653 Squarefree

$O(R^{1/3}+(R-L))$ 解

問題

https://yukicoder.me/problems/no/1653

解法

square-free でない数

$x$ は整数

$i,j$ を使って

$x=i^2\times j$ と表すことができます。

$i^2\times j\le R$ のとき、適当な定数

$r$ を決めると、

$i\le r$ または

$j\le R/r^2$ が成り立ちます。

$i\le r$ の範囲は

$i$ を、

$j\le R/r^2$ の範囲は

$j$ をはじめに固定して探索します。

解析

$L\le i^2\times j\le R$ となる

$(i,j)$ の個数は

$$O\left(\sum _{i=1}^{\mathrm{\infty }}\frac{R-L}{i^2}\right)=O((R-L)\zeta (2))=O(R-L)$$

しかないことが重要です。

$L\le i^2\times j\le R$ となる範囲は連続かつどちらかを固定すると

$O(1)$ で計算できる (←モデルによる) ので、計算量は、これと、はじめに固定する

$i$ の個数と、はじめに固定する

$j$ の個数で、

$O((R-L)+r+R/r^2)$

$r\in \mathrm{\Theta }(R^{1/3})$ とすれば

$O(R^{1/3}+(R-L))$

実装

$i$ を整数ではなく素数として、先に Atkin の篩で素数列挙をしてから前半をやると速い
後半は

$j$ を固定すると調べる必要のある

$i$ はこの制約下で高々

$1$ 個である

$i>r$ の範囲しか調べる必要がない。

$i>r$ のとき

$(i+1{)}^2-i^2=2i+1>2r+1$ より、

$2r\ge R-L$ であれば高々

$1$ 個。

C++, 15 ms https://yukicoder.me/submissions/692585