AOJ 1232 - Calling Extraterrestrial Intelligence Again

問題概要

3つの整数 $m,a,b$ が与えられます。
$pq \leqq m$ かつ $a/b \leqq p/q \leqq 1$ となるような $(p,q)$ のうち、 $pq$ が最大となるようなペアを求めてください。
制約は、 $4 \lt m \lt 100000, 1 \leqq a \leqq b \leqq 1000$ です。

解法

まずはエラトステネスの篩を利用して、素数を洗い出します。
$q$ について全探索をすると、 $p$ の最適解は、ある $q$ に対して、
$p \leqq m/q$ 、 $aq/b \leqq p \leqq q$ を満たすような最大の素数になります。
ので、二分探索で $p$ の最大値を毎回求め、答えを求めていけばよいです。

のですが、AC後に他の解説ブログを見たところ、 $m/q$ という制約のおかげで、 $p$ も全探索できるらしいです…ちょうど調和級数の形になりますね。