G - sqrt(n²+n+X) Editorial by en_translator
Let \(m = \sqrt{n^2+n+X}\). Under \(m \geq 0\), one can apply equivalence transformations as follows:
\[ \begin{aligned} &\phantom{\Leftrightarrow} m = \sqrt{n^2+n+X}\\ &\Leftrightarrow m^2=n^2+n+X\\ &\Leftrightarrow (2m+2n+1)(2m-2n-1)=4X-1\\ \end{aligned} \]
Therefore, we enumerate all divisors \(d\) of \(4X-1\) (including negative divisors), and check for each of them whether there exists an integer pair \((n,m)\) such that \(\displaystyle 2m+2n+1=d,\ 2m-2n-1=\frac{4X-1}d\), and \(m \geq 0\); those integers \(n\) found by this enumeration are the solutions.
This problem can be solved by properly implementing this algorithm. The time complexity is \(O(\sqrt X)\).
x = int(input())
ans = []
c = 4 * x - 1
def add(d):
ans.append((d - c // d - 2) // 4)
d = -1
while d * d <= abs(c):
d += 2
if c % d != 0:
continue
add(d), add(-d)
add(c // d), add(-c // d)
ans = sorted(list(set(ans)))
print(len(ans))
print(*ans)
posted:
last update: