题目分析

若 $k = 0$，答案显然为 $0$。

若 $k > 0$，设序列的第 $x + 1$ 项为平方数，则存在正整数 $y$，使得 $k + x^2 = y^2$，于是 $k = y^2 - x^2 = (y + x)(y - x)$，于是枚举 $k$ 的所有不超过 $\sqrt{k}$ 的正因数 $i$，那么就可以令 $y + x = i , y - x = k \div i$，解得 $y = (i + k \div i) \div 2$，最后取所有 $y$ 的最小值即可。

若 $k < 0$，设序列的第 $x + 1$ 项为平方数，则存在正整数 $y$，使得 $- \left| k \right| + x^2 = y^2$，于是 $\left| k \right| = x^2 - y^2 = (x + y)(x - y)$，于是枚举 $\left| k \right|$ 的所有不超过 $\sqrt{\left| k \right|}$ 的正因数 $i$，那么就可以令 $x + y = \left| k \right| \div i , x - y = i$，解得 $y = \left| k \right| \div i - (i + \left| k \right| \div i) \div 2$，最后取所有 $y$ 的最小值即可。注意这里不令 $x + y = i , x - y = \left| k \right| \div i$ 的原因是这种情况下解得 $y = i - (i + \left| k \right| \div i) \div 2$，但这是负数（因为 $i \le \sqrt{\left| k \right|}$）。

注意判断无解。时间复杂度为 $O(\sqrt{\left| k \right|})$。

参考代码

#include<iostream>
#define int long long
using namespace std;
int k;
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>k;
	if(k==0) cout<<0;
	else if(k>0){
		int ans=1e18;
		for(int i=1;i*i<=k;i++){
			if(k%i==0){
				if((i+k/i)%2==0) ans=min(ans,(i+k/i)/2);
			}
		}
		if(ans==1e18) cout<<"none";
		else cout<<ans;
	}else{
		k*=-1;
		int ans=1e18;
		for(int i=1;i*i<=k;i++){
			if(k%i==0){
				if((i+k/i)%2==0) ans=min(ans,k/i-(i+k/i)/2);
			}
		}
		if(ans==1e18) cout<<"none";
		else cout<<ans;
	}
	return 0;
}