Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 250 D問題 250-like Number

AtCoder ABC ABC250 D問題 400 pts

問題

提出解答

問題の概要

次を満たす $N$ 以下の整数 $k$ の個数を求めよ.

次を満たす素数 $p,q$ が存在する: $p \lt q, k=pq^3$

制約

$1 \leq N \leq 10^{18}$

解法

素因数分解の一意性から, 求めるべき答えは $p \lt q$ なる素数 $pq^3$ の形で表せる $N$ 以下の整数である.

$q$ の範囲について, 素数は $2$ 以上なので, $q^3 \leq pq^3=k \leq N$ より, $q \leq \sqrt[3]{N}$ である.

$M:=\sqrt[3]{N}$ とする. $M$ 以下の素数 $q$ を固定する. このとき, $\min\left(q-1, \dfrac{N}{q^3} \right)$ 以下の素数 $p$ に対して, $pq^3$ は必ず条件を満たす.

ここで, 素数 $p,p',q,q'$ について, $(p,q) \neq (p',q')$ ならば, $pq^3 \neq p' q'^{3}$ であるから, この方法で同じ整数を $2$ 回数えてしまうことはない.

以上から, $M$ 以下の素数と, $M$ 以下の整数 $x$ に対して, $x$ 以下の素数の個数を求めることができればよい. $M$ 以下の素数は Eratosthenes の篩を利用することにより, 計算量 $O(M \log \log M)$ で全て求めることができ, $x$ 以下の素数の個数は今求めた $M$ 以下の素数を利用して, 累積和で計算量 $O(M)$ で計算できる.

以上から, 時間計算量 $O(M \log \log M)=O(\sqrt[3]{N} \log \log N)$ で求めることができた.