专栏文章

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

wweifengzhaomi
AT_abc420_g题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio57pyw
此快照首次捕获于
2025/12/02 13:33
3 个月前
此快照最后确认于
2025/12/02 13:33
3 个月前
查看原文
我膨胀了！我敢给 G 题写题解了！

题意

题意很简单，就是给你一个正整数 xx，你要找出所有的正整数 nn，使得 n2+n+x\sqrt{n ^ 2 + n + x} 是一个正整数。
−1014≤x≤1014-10 ^ {14} \le x \le 10 ^ {14}。

思路

要使得 n2+n+x\sqrt{n ^ 2 + n + x} 是一个正整数，那么 n2+n+xn ^ 2 + n + x 一定可以表示成某个数的平方。
n2+n+x=m2n ^ 2 + n + x = m ^ 2
我们想办法把 n2+nn ^ 2 + n 给拆成一个平方差在求解。
4n2+4n=4m2−4x4n ^ 2 + 4n = 4m ^ 2 - 4x
(2n+1)2=4m2−4x−1(2n + 1) ^ 2 = 4m ^ 2 - 4x - 1
4m2−(2n+1)2=4x−14m ^ 2 - (2n + 1) ^ 2 = 4x - 1
很明显，m2−(2n+1)2m ^ 2 - (2n + 1) ^ 2 可以用平方差公式来分解。
(2m−2n−1)(2m+2n+1)=4x−1(2m - 2n - 1)(2m + 2n + 1) = 4x - 1
到这里，这道题就做完了。
两个乘数我们只要枚举其中一个即可，只要枚举到的是 4x−14x - 1 的因子，那么我们就可以算出另一个乘数。
然后，我们计算出可能的值，加入到答案中，再去个重就好了。

代码

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y,z;
set<int> ans;
signed main(){
    cin >> x,y = 4 * x - 1,z = abs(y);
    if (!y) return printf("0\n"),0;
    for (int i = 1;i * i <= z;i++)
        if (z % i == 0){
			int a = i,b = y / i,c = b - a - 2;
            if (c % 4 == 0 && a % 2 == 1 && b % 2 == 1) ans.insert(c / 4);
			a = -i,b = -y / i,c = b - a - 2;
            if (c % 4 == 0 && a % 2 == 1 && b % 2 == 1) ans.insert(c / 4);
            a = z / i,b = y / (z / i),c = b - a - 2;
            if (c % 4 == 0 && abs(a % 2) == 1 && abs(b % 2) == 1) ans.insert(c / 4);
            a = -z / i,b = -y / (z / i),c = b - a - 2;
            if (c % 4 == 0 && abs(a % 2) == 1 && abs(b % 2) == 1) ans.insert(c / 4);
        }
    cout << ans.size() << endl;
    for (auto y : ans) cout << y << " ";
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...