公式

G - sqrt(n²+n+X) 解説 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)\).

Sample code (Python3)

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)

投稿日時:
最終更新: