---
tags: yukicoder
---
# 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 ≤ R$ のとき、適当な定数 $r$ を決めると、$i ≤ r$ または $j ≤ R / r^2$ が成り立ちます。
$i ≤ r$ の範囲は $i$ を、$j ≤ R / r^2$ の範囲は $j$ をはじめに固定して探索します。

## 解析

$L ≤ i^2 \times j ≤ R$ となる $(i, j)$ の個数は

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

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

$L ≤ i^2 \times j ≤ R$ となる範囲は連続かつどちらかを固定すると $O(1)$ で計算できる (←モデルによる) ので、計算量は、これと、はじめに固定する $i$ の個数と、はじめに固定する $j$ の個数で、$O((R - L) + r + R/r^2)$

$r \in \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 ≥ R - L$ であれば高々 $1$ 個。

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