Kazun の競プロ記録

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

AtCoder Beginner Contest 227 C 問題 ABC conjecture

AtCoder ABC ABC227 C問題 300 pts

問題

提出解答

問題の概要

正の整数の組 $(A,B,C)$ で, 以下を満たすのはいくつか?

$A \leq B \leq C$
$ABC \leq N$

制約

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

解法

$A \leq B \leq C$ より,

$A^3 \leq A \cdot A \cdot A \leq A \cdot B \cdot C \leq N$

から, $A^3 \leq N$ . つまり, $A \leq \sqrt[3]{N}$ である. よって, $A=1,2,\dots, \lfloor \sqrt[3]{N} \rfloor$ と固定した場合それぞれについて見ればよい.

$A=\alpha~(1 \leq \alpha \leq \lfloor \sqrt[3]{N} \rfloor)$ と固定する. このとき, $BC \leq \dfrac{N}{\alpha}$ であり, $B \leq C$ から, $B \leq \sqrt{\dfrac{N}{\alpha}}$ でなくてはならない. $B=\beta$ と固定する. このとき, $C$ は

$\beta \leq C \leq \dfrac{N}{\alpha \beta}$

この不等式を満たすような $C$ の個数は $\left \lfloor \dfrac{N}{\alpha \beta} \right \rfloor-\beta+1$ 個である *1.

以上のことから, 以下のようにして正解を導くことができる.

$X \gets 0$
に対して, 以下を実行する.
- に対して, 以下を実行する.
  - $X$ に $\left \lfloor \dfrac{N}{\alpha \beta} \right \rfloor-\beta+1$ を加算する.

計算量は, $O(N^{2/3})$ であり, $N \leq 10^{11}$ なので, 下手に実装しなければ間に合う.

*1: $\beta \leq \sqrt{\dfrac{N}{\alpha}}$ より, 実数の世界では大小関係は崩れない.