AT_abc420_g [ABC420G] sqrt(n²+n+X)

思路

数学题。

设 $N^2 + N + X = (N + a)^2$，则：

$\begin{aligned} N^2 + N + X&=N^2 + 2aN + a^2\ N + X &= 2aN + a^2\ (2a - 1) N &= X - a^2\ N &= \dfrac{X - a^2}{2a - 1}. \end{aligned}$

枚举 $a$ 从 $-\sqrt{2\lvert X \rvert + 1}$ 至 $\sqrt{2\lvert X \rvert + 1}$，判断 $(X - a^2) \bmod (2a - 1)$ 是否为 $0$，并记录满足条件的 $N$。

---

接下来是 $a$ 的取值范围[^1]的证明。

首先 $a = -N \pm \sqrt{N^2 + N + X}$。

$N > 0$ 时，取 $a = -N + \sqrt{N^2 + N + X}$。

则 $a = \sqrt{N^2 + N + X} - \sqrt{N^2}$。

当 $a > 0$ 时，显然有 $a \leq \sqrt{N+X}$ [^2]。

当 $a < 0$ 时，$-a = \sqrt{N^2} - \sqrt{N^2 + N + X}$。

我们将式子写成 $ -a = \sqrt{N^2 + N + X + (-N - X)} - \sqrt{N^2 + N + X}$。

显然有 $-a \leq \sqrt{-N - X}$。

综上，$\lvert a \rvert \leq \sqrt{\lvert N + X \rvert} \leq \sqrt{\lvert N \rvert + \lvert X \rvert}$。

可以证明 $\lvert N \rvert \leq \lvert X \rvert+1$。

因此 $\lvert a \rvert\leq \sqrt{2\lvert X \rvert + 1}$，即 $a \in [-\sqrt{2\lvert X \rvert + 1},\sqrt{2\lvert X \rvert + 1}]$。

$N < 0$ 时，取 $a = −N - \sqrt{ N^2 + N + X }$。

则 $-a = \sqrt{N^2 + N + X} - \sqrt{N^2}$。

同样可以得出 $a \in [-\sqrt{2\lvert X \rvert + 1},\sqrt{2\lvert X \rvert + 1}]$。证毕。

---

upd 2025.08.27：似乎可以证明 $a \in [-\sqrt{\lvert X \rvert + 1},\sqrt{\lvert X \rvert + 1}]$，但枚举 $a \in [-\sqrt{2\lvert X \rvert + 1},\sqrt{2\lvert X \rvert + 1}]$ 保证能求出所有解。

Code

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=1.5e7+10;

int x;

int tot,ans[N];

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
	return ret*f;
}

signed main(){
	x=read();
	int X=abs(x);
	for(int i=ceil(-sqrtl(X*2+1));i*i<=X*2+1;i++){
		if((x-i*i)%(i*2-1)==0){
			ans[++tot]=(x-i*i)/(i*2-1);
		}
	}
	sort(ans+1,ans+tot+1);
	tot=unique(ans+1,ans+tot+1)-ans-1;
	printf("%lld\n",tot);
	for(int i=1;i<=tot;i++)printf("%lld ",ans[i]);
	printf("\n");
	return 0;
}

注释

[^1]:枚举该范围内的 $a$ 即可求出所有符合条件的 $N$，并非所有 $a$ 都在该范围内。

[^2]:当 $A,B > 0$ 时，$\sqrt{A+B} - \sqrt{A} \leq \sqrt{B}$。