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

· · 题解

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

题目链接

转至专栏阅读

解题思路

设 \sqrt{n²+n+X} 的值为 m (其中 m \ge 0)，那么题目的条件可以写成一个方程：

n^2 + n + X = m^2

将等式两边同乘 4 得：

4n^2 + 4n + 4X = 4m^2

配方得：

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

将左边用平方差展开得：

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

令 d_1 = 2m - (2n+1),d_2 = 2m + (2n+1)。由于 n 和 m 都是整数，所以 d_1 和 d_2 也必须是整数。这说明 d_1 和 d_2 必须是 4X-1 的一对整数因子。

将定义 d_1 和 d_2 的两个式子相减得：

d_2 - d_1 = (2m + 2n + 1) - (2m - 2n - 1) = 4n + 2

相加得：

d_1 + d_2 = (2m - 2n - 1) + (2m + 2n + 1) = 4m

解得：

n = \frac{d_2 - d_1 - 2}{4},m=\frac{d_1 + d_2}{4}

为了让 n,m 都是整数，d_2 - d_1 - 2 和 d_1 + d_2 都必须是 4 的倍数。

因为 d_1 \cdot d_2 = 4X - 1，是奇数，所以只要保证 d_1 + d_2 是 4 的倍数，d_2 - d_1 - 2 就是 4 的倍数。

综上，我们需要枚举 4X - 1 的每一对因子，检查他们的和能否被 4 整除，然后算出所有 n，去重后输出。

时间复杂度 O(\sqrt{|X|})。

参考代码

#include<iostream>
#include<set>
#define int long long 
using namespace std;
int x;
set<int> ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>x;
    int d=4*x-1,p=abs(d);
    for(int i=1;i*i<=p;i++){
        if(p%i==0){
            int j=p/i;
            if(d>0){
                if((i+j)%4==0){
                    ans.insert((j-i-2)/4);
                    ans.insert((i-j-2)/4);
                }
            }
            else{
                if((j-i)%4==0){
                    ans.insert((j+i-2)/4);
                    ans.insert((-i-j-2)/4);
                }
            }
        }
    }
    cout<<ans.size()<<'\n';
    for(int i:ans) cout<<i<<' ';
    return 0;
}

AC 记录