题解：AT_abc420_g [ABC420G] sqrt(n²+n+X)

q1uple 随手切了，膜拜。

推式子：

m=\sqrt{n^2+n+x}

去根号：

m^2=n^2+n+x

(2m)^2=(2n)^2+4n+4x

(2m)^2=(2n+1)^2+4x-1

(2m)^2-(2n+1)^2=4x-1

把左边写成

(a+b)(a-b)

的形式：

(2m+2n+1)(2m-2n-1)=4x-1

考虑把

4x-1

拆成

a\times b

，使得存在非负整数

m

、整数

n

满足：

2m+2n+1=a \\ 2m-2n-1=b \end{matrix}\right.$$ 枚举 $a,b$ 仅需 $\sqrt X$ 的时间复杂度。注意判重。 ```cpp #include<bits/stdc++.h> #define int long long #define mp(a,b) make_pair(a,b) using namespace std; inline int read(){ int a=0,b=1; char c=getchar(); while(!isdigit(c)){ if(c=='-') b=-1; c=getchar(); } while(isdigit(c)){ a=(a<<1)+(a<<3)+(c-'0'); c=getchar(); } return a*b; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>=10) write(x/10); putchar(x%10+48); } inline void write1(int x){ write(x),putchar(' '); } inline void write2(int x){ write(x),putchar('\n'); } vector<int> include13; signed main(){ int n=read()*4-1; for(int i=-2e7;i<=2e7;i++){ if(i==0) continue; int a=i,b=n/i; if(a*b==n){ if((a-b-2)%4==0){ include13.push_back((a-b-2)/4); } } } sort(include13.begin(),include13.end()); int include13_fAKe=0; for(int i=1;i<include13.size();i++){ if(include13[i]!=include13[i-1]) include13_fAKe++; } write2(include13_fAKe+1); write1(include13[0]); for(int i=1;i<include13.size();i++){ if(include13[i]!=include13[i-1]) write1(include13[i]); } putchar('\n'); return 0; }//ABC420G 一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！ ```

文章操作