题解：AT_abc420_g [ABC420G] sqrt(n²+n+X)
weifengzhaomi
·
·
题解
我膨胀了！我敢给 G 题写题解了！
题意
题意很简单，就是给你一个正整数 x，你要找出所有的正整数 n，使得 \sqrt{n ^ 2 + n + x} 是一个正整数。
## 思路
要使得 $\sqrt{n ^ 2 + n + x}$ 是一个正整数，那么 $n ^ 2 + n + x$ 一定可以表示成某个数的平方。
$$n ^ 2 + n + x = m ^ 2$$
我们想办法把 $n ^ 2 + n$ 给拆成一个平方差在求解。
$$4n ^ 2 + 4n = 4m ^ 2 - 4x$$
$$(2n + 1) ^ 2 = 4m ^ 2 - 4x - 1$$
$$4m ^ 2 - (2n + 1) ^ 2 = 4x - 1$$
很明显，$m ^ 2 - (2n + 1) ^ 2$ 可以用平方差公式来分解。
$$(2m - 2n - 1)(2m + 2n + 1) = 4x - 1$$
到这里，这道题就做完了。
两个乘数我们只要枚举其中一个即可，只要枚举到的是 $4x - 1$ 的因子，那么我们就可以算出另一个乘数。
然后，我们计算出可能的值，加入到答案中，再去个重就好了。
## 代码
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y,z;
set<int> ans;
signed main(){
cin >> x,y = 4 * x - 1,z = abs(y);
if (!y) return printf("0\n"),0;
for (int i = 1;i * i <= z;i++)
if (z % i == 0){
int a = i,b = y / i,c = b - a - 2;
if (c % 4 == 0 && a % 2 == 1 && b % 2 == 1) ans.insert(c / 4);
a = -i,b = -y / i,c = b - a - 2;
if (c % 4 == 0 && a % 2 == 1 && b % 2 == 1) ans.insert(c / 4);
a = z / i,b = y / (z / i),c = b - a - 2;
if (c % 4 == 0 && abs(a % 2) == 1 && abs(b % 2) == 1) ans.insert(c / 4);
a = -z / i,b = -y / (z / i),c = b - a - 2;
if (c % 4 == 0 && abs(a % 2) == 1 && abs(b % 2) == 1) ans.insert(c / 4);
}
cout << ans.size() << endl;
for (auto y : ans) cout << y << " ";
}
```