Kazun の競プロ記録

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

AtCoder Beginner Contest 296 D問題 M<=ab

AtCoder ABC ABC296 C問題 300 pts

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

問題

提出解答

問題の概要

次の条件を満たす整数 $X$ は存在するか? 存在するならば, そのような $X$ のうちの最小値を求めよ.

$X \geq M$
$1$ 以上 $N$ 以下の整数 $a,b$ が存在して, $X=ab$ である.

制約

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

解法

まず, 存在性について, 以下が成り立つ.

条件を満たすような整数 $X$ が存在することと, $M \leq N^2$ であることは同値である.

(証明)

$M \leq N^2$ のとき, $(a,b)=(N,N)$ とすれば, $1 \leq a,b \leq N$ であり, $ab=N^2 \geq M$ である.
条件を満たすような整数 $X$ に対して, $X=ab$ であったとする. このとき, $1 \leq a,b \leq N$ より, $X \leq N^2$ である. よって, $M \leq X$ でもあったので, $M \leq N^2$ となる.

これ以降では存在性は仮定する. つまり, $M \leq N^2$ を仮定する.

ここで, 対称性から $a \leq b$ の追加条件を課してもよいことがわかる. そして, このとき, 最小値 $X$ に対して $X=ab, a \leq b$ とすると, $a \leq \lceil \sqrt{M} \rceil$ を満たす. 実際, $a \gt \rceil \sqrt{M} \rceil$ とすると,

$M \leq \lceil \sqrt{M} \lt \leq a^2 \leq ab$

となり, より小さい整数が条件を満たすことがわかる.

$a$ をある $\sqrt{M}$ 以下の正の整数に固定する. このとき, $b$ としては $a \gt 0$ であるから, $b$ は $ab \geq M$ を満たす条件下ではなるべく小さくしたい. これは $\left \lceil \frac{M}{a} \right \rceil \leq N$ のときに実現可能で, $b=\left \lceil \frac{M}{a} \right \rceil$ が最適である.

よって, 求めるべきは

$\displaystyle \min_{\substack{1 \leq a \leq \sqrt{M} \\ \left \lceil \frac{M}{a} \right \rceil \leq N}} a \left \lceil \frac{M}{a} \right \rceil$

である.