题解：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 的时间复杂度。注意判重。

#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 一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！