初めに

atcoder.jp 解゛け゛ま゛せ゛ん゛で゛し゛た゛...

敗因

最初は変な風に誤読をしていて 2 ペナをしました.

そのあとある数 $x$ が与えられるのでそれが $[1, N ]$ に存在するふたつの数の積で表せるかを判定する関数みたいなものをつくりました.

当然, 最後の方は $N \cdot ( N \, - \, 1 )$ と $N \cdot N$ の間にはそのような $x$ は存在しないので最悪 $O( \, N \, )$ になります.

このことに気づいたのが 22:00 くらいでした.

かなり焦っていたのもあってうまく思考できず... 完全に敗北です.

a を固定します. そうすると b が $O( \, 1 \, )$ に定まります. $a \, \le \, b$ として一般性を失わないので結局 $O( \, \sqrt{M} \,)$ となって十分高速です. atcoder.jp

あーあ