Kazun の競プロ記録

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

AtCoder Beginner Contest 300 D問題 AABCC

AtCoder ABC ABC300 D問題 400 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

次を見たす整数 $n$ の数を求めよ.

$1 \leq n \leq N$
$a \lt b \lt c$ なる素数 $a,b,c$ に対して, $n=a^2 b c^2$ となる.

制約

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

解法

$1$ 以上 $N$ 以下の整数 $n$ が $a \lt b \lt c$ となる素数 $a,b,c$ に対して, $n=a^2 b c^2$ と表されるとき,

$a^5 \leq a^2 b c^2=n \leq N, \quad b^3 \leq a^2 b c^2=n \leq N, c^2 \leq a^2 b c^2=n \leq N$

であるから, $a \leq \sqrt[5]{N}, b \leq \sqrt[3]{N}, c \leq \sqrt{N}$ となる.

よって, $a \leq \sqrt[5]{N}, b \leq \sqrt[3]{N}, a \lt b$ となる各素数の組 $(a,b)$ に対して, $\displaystyle b \lt c \leq \sqrt{\dfrac{N}{a^2 b}}=:K$ となる素数 $c$ の数を高速に計算できれば良い.

これは $P(n)$ を $n$ 以下の素数とすると,

$b \leq K$ ならば, $S(K)-S(b)$ 個
$b \lt K$ ならば, $0$ 個

である.

ここで, $S(n)$ は $n \leq \sqrt{N}$ の範囲まで求めれば良く, これはエラトステネスの篩を利用することで $O(\sqrt{N})$ 時間で求められる.

また, 調べるべき $(a,b)$ の数は高々 $\sqrt[5]{N} \times \sqrt[3]{N}=N^{8/15}$ 組である.

以上から, $O(N^{8/15})$ 時間で求めることができた