题目大意

给出一个数 XX ，求出所有的nn，使得$ \sqrt{n^2+n+X} $ 是一个整数

解题思路

不难发现，nn一定是个整数

因为$ \sqrt{n^2+n+X} $ 是一个整数，所以我们可以把n2+n+Xn^2+n+X用(n+m)2(n+m)^2表示出来（其中mm是一个整数）

所以，n+X=n2+n+X−n2=(n+m)2−n2=2nm+m2n+X=n^2+n+X-n^2=(n+m)^2-n^2=2nm+m^2

所以 X−m2=2nm−n=(2m−1)nX-m^2=2nm-n=(2m-1)n

我们可以考虑枚举mm，判断X−m22m−1\frac{X-m^2}{2m-1}是否是一个整数，如果是的话，就说明nn是个整数，最后统计完之后排序去重就可以了。

时间复杂度分析

因为−1014≤X≤1014-10^{14} \leq X \leq 10^{14},所以$ \sqrt{n^2+n+X} $最大约是10710^7,所以n+mn+m最大值也约是10710^7，所以mm的最大值也大概是10710^7

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF=2e7+10;
int x;
vector<int> ans;
signed main(){
    cin>>x;
    for(int i=0;i<=INF;i++){
        if((x-i*i)%(2*i-1)==0) ans.push_back((x-i*i)/(2*i-1));
        i=-i;
        if((x-i*i)%(2*i-1)==0) ans.push_back((x-i*i)/(2*i-1));
        i=-i;
    }
    sort(ans.begin(),ans.end());
    ans.erase(unique(ans.begin(),ans.end()),ans.end());
    cout<<ans.size()<<endl;
    for(auto i:ans) cout<<i<<' ';
    return 0;
}