No.004 C

$X, Y$ は最大公約数で割って互いに素にしておく.

誤って出した答えは

$$\frac{X}{Y} = \frac{N+1}{2}-\frac{M}{N}$$

となるので,

$$M = \frac{N(N+1)}{2} - \frac{NX}{Y}$$

となる. 右辺第一項は整数なので, 右辺第二項も整数でなければならず, $N$ は $Y$ の倍数でなければならない.

そこで, $N = kY$ とすると,

$$\begin{align} M &= \frac{kY(kY+1)}{2} - kX \\ &= \frac{1}{2}k(Y^2k + Y-2X) \end{align}$$

となり, $0 \lt M \leq N$ という条件から,

$$\frac{2X}{Y^2}-\frac{1}{Y} \lt k \leq \frac{2X}{Y^2}+\frac{1}{Y}$$

となるので, $k$ の候補は高々2つであることがわかる.

よって, $\lfloor 2X/Y^2 \rfloor - 1$ から $\lceil 2X/Y^2 \rceil + 1$ の範囲で $k$ を調べ, そのときの $M$ が正しい範囲にあるかどうかを確認すればいい.