专栏文章

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

XXCDRF
AT_abc420_g题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@mio5heby
此快照首次捕获于
2025/12/02 13:41
3 个月前
此快照最后确认于
2025/12/02 13:41
3 个月前
查看原文

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

题目链接
转至专栏阅读

解题思路

设 n2+n+X\sqrt{n²+n+X} 的值为 mm (其中 m≥0m \ge 0)，那么题目的条件可以写成一个方程： n2+n+X=m2n^2 + n + X = m^2
将等式两边同乘 44 得：
4n2+4n+4X=4m24n^2 + 4n + 4X = 4m^2
配方得： (4n2+4n+1)−1+4X=4m2(4n^2 + 4n + 1) - 1 + 4X = 4m^2 (2n+1)2−1+4X=(2m)2(2n+1)^2 - 1 + 4X = (2m)^2 (2m)2−(2n+1)2=4X−1(2m)^2 - (2n+1)^2 = 4X - 1
将左边用平方差展开得： (2m−(2n+1))(2m+(2n+1))=4X−1(2m - (2n+1))(2m + (2n+1)) = 4X - 1
令 d1=2m−(2n+1),d2=2m+(2n+1)d_1 = 2m - (2n+1),d_2 = 2m + (2n+1)。由于 nn 和 mm 都是整数，所以 d1d_1 和 d2d_2 也必须是整数。这说明 d1d_1 和 d2d_2 必须是 4X−14X-1 的一对整数因子。
将定义 d1d_1 和 d2d_2 的两个式子相减得： d2−d1=(2m+2n+1)−(2m−2n−1)=4n+2d_2 - d_1 = (2m + 2n + 1) - (2m - 2n - 1) = 4n + 2 相加得： d1+d2=(2m−2n−1)+(2m+2n+1)=4md_1 + d_2 = (2m - 2n - 1) + (2m + 2n + 1) = 4m
解得： n=d2−d1−24,m=d1+d24n = \frac{d_2 - d_1 - 2}{4},m=\frac{d_1 + d_2}{4}
为了让 n,mn,m 都是整数，d2−d1−2d_2 - d_1 - 2 和 d1+d2d_1 + d_2 都必须是 44 的倍数。
因为 d1⋅d2=4X−1d_1 \cdot d_2 = 4X - 1，是奇数，所以只要保证 d1+d2d_1 + d_2 是 44 的倍数，d2−d1−2d_2 - d_1 - 2 就是 44 的倍数。
综上，我们需要枚举 4X−14X - 1 的每一对因子，检查他们的和能否被 44 整除，然后算出所有 nn，去重后输出。
时间复杂度 O(∣X∣)O(\sqrt{|X|})。

参考代码

CPP
#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 记录

评论

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

正在加载评论...