题解：AT_abc420_g [ABC420G] sqrt(n²+n+X)

simple_child · 2025-08-25 14:45:55 · 题解

给定整数 X(-10^{14} \leq X \leq 10^{14})。请求出所有满足 \sqrt{n^2 + n + X} 为整数的整数 n。

数学题。也是我 ABC 过的第一个 G。
令 m=\sqrt{n^2 + n + X}，即 m^2=n^2 + n + X，同时乘 4 可得 4m^2=4n^2 + 4n + 4X，即 4m^2=(2n+1)^2-1+4X，也就是 4m^2-(2n+1)^2=4X-1，展开后可得(4m+2n+1)(4m-2n-1)=4X-1。再令 d=4X-1，则问题转化为找到整数对 (a,b) 使得 a×b=d 且 b−a≡2 \pmod4。
接下来就很清晰了。我们计算 d 的绝对值的所有因子，对于每个因子 p，考虑 a=p 和 a=-p 两种情况，计算对应的 b=d÷a。对于每个因子对 (a,b)，判断(b−a)\mod4 是否等于 2，若满足条件，则将 (b-a-2) 的值加入 set。
最后输出 set 即可。

C++通过代码。