Finding $2m+1=2\alpha k+\alpha^2$ quickly

Question

Given some positive integer $m$ I'm looking for all solutions $\alpha,k>0$ to $2m+1=2\alpha k+\alpha^2$ with $0<k^2<2m.$ Right now I'm finding these by looping over each of these possible $k$ values and testing if the resulting quadratic has a solution, but I feel that something more clever would be faster. Any ideas?

You can assume that $m$ is large, e.g. $m>10^6,$ if it helps.

Answer 1

you can solve the quadratic equation in α. For integer solutions, we must have k^2 + 2m +1 = a perfect square. You then have a solution when k=m since then k^2 + 2k + 1 = (k+1)^2.

Answer 2

For a discriminant to be a perfect square you need $k^2 + 2m + 1 = n^2$, that is $2m + 1 = (n+k)(n-k)$. In other words, factorize $2m + 1$; for each divisor $d < \sqrt{2m + 1}$ there is a solution $k = \frac{\frac{2m + 1}{d} - d}{2}$. It is still $O(\sqrt{2m})$ loop, but instead of testing a quadratic you only need to test for divisibility.