Codeforces Round #332 (Div. 2) D. Spongebob and Squares

幅$w$、高さ$h$,$h\le w$の長方形の中に正方形は$h(h+1)(3w-h+1)/6$個ある。そのため、

$$ \frac{h(h+1)(3w-h+1)}{6}=x $$

を満たす$w,h$を求める問題に帰着できる。

$6x=pq$とすると、$h=p,\; (h+1)(3w-h+1)=q$なので、 $$h=p,\;w=\frac{p^2+q-1}{3(p+1)}$$

とわかる。$h\le w$なので$w=(p^2+q-1)/3(p+1) \ge p=h $が成り立つ。よって

$$ 6x = pq \ge 2p^3+3p^2+p $$

という条件が導ける。$p=3\cdot10^6$は条件を満たさないので、$p\le3\cdot10^6$までを全探索すればいい。

$x=wh(h+1)/2+h(h-1)(h+1)/6$を使った方が上の議論はシンプルになると思う。ぱっと見は$O(\sqrt{n})$だけどよく考えると$O(\sqrt[3]{n})$という問題をSRMで解いてたので割りとすぐ気づけた。