sqrt(n²+n+X)题解
wenzhenhao
·
·
题解
题目传送门
题目大意
输入一个数 X ，求出所有 n 使得 \sqrt{n^{2}+n+X} 为正整数。
解题思路
令 k=\sqrt{n^{2}+n+X}。
则 k^{2}=n^{2}+n+X。
将等式两边同时乘以 4 ，得 4n^{2}+4n+1+4X-1=4k^{2}。
接着配方，得 (2n+1)^{2}+(4X-1)=(2k)^2。
即 (2k)^2-(2n-1)^{2}=4X-1。
通过平方差公式，得 (2k-2n-1)\times(2k+2n+1)=4X-1。
令 a=2k-2n-1\;\;b=2k+2n+1：
$\frac{1}{4}(\pm(b-a)-2)\begin{cases}\frac{1}{4}(b-a-2)=\frac{1}{4}(4n)=n_{1}\\\frac{1}{4}(a-b-2)=\frac{1}{4}(4n)=n_{2}\end{cases}
---
#### 解题代码
由于$a\times b=C$，所以只需要遍历`for(int a=1;a<=C_sqrt;i++)`，其中 `C_sqrt` $=\sqrt{C}$ 。
考虑 $a,b$ 的正负性，我们`insert(a,b)`和`insert(-b,-a)` 其中 $a\le b$。
实例代码使用`set`处理重复数字：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
set<ll>solutions;
void func(ll a,ll b)
{
if(a>b)
swap(a,b);
if((a+b)%4==0)
{
ll n1=(b-a-2)/4;
ll n2=(a-b-2)/4;
solutions.insert(n1);
solutions.insert(n2);
}
}
int main()
{
ll X;
cin>>X;
ll C=4*X-1;
if(C==0)
return 0;
ll sqrt_C=sqrt(abs(C));
for(ll i=1;i<=sqrt_C;i++)
{
if(C%i==0)
{
ll b=C/i;
func(i,b);
func(-b,-i);
}
}
cout<<solutions.size()<<endl;
for(ll q:solutions)
cout<<q<<" ";
return 0;
}
```
该程序时间复杂度约为 $O(\sqrt{4X-1})$。
完结撒花!