专栏文章

sqrt(n²+n+X)题解

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mio5bvl5
此快照首次捕获于
2025/12/02 13:37
3 个月前
此快照最后确认于
2025/12/02 13:37
3 个月前
查看原文
题目传送门

题目大意

输入一个数 XX ，求出所有 nn 使得 n2+n+X\sqrt{n^{2}+n+X} 为正整数。

解题思路

令 k=n2+n+Xk=\sqrt{n^{2}+n+X}。
则 k2=n2+n+Xk^{2}=n^{2}+n+X。
将等式两边同时乘以 44 ，得 4n2+4n+1+4X−1=4k24n^{2}+4n+1+4X-1=4k^{2}。
接着配方，得 (2n+1)2+(4X−1)=(2k)2(2n+1)^{2}+(4X-1)=(2k)^2。
即 (2k)2−(2n−1)2=4X−1(2k)^2-(2n-1)^{2}=4X-1。
通过平方差公式，得 (2k−2n−1)×(2k+2n+1)=4X−1(2k-2n-1)\times(2k+2n+1)=4X-1。
令 a=2k−2n−1    b=2k+2n+1a=2k-2n-1\;\;b=2k+2n+1:
14(a+b)=14(4k)=k\frac{1}{4}(a+b)=\frac{1}{4}(4k)=k
14(±(b−a)−2){14(b−a−2)=14(4n)=n114(a−b−2)=14(4n)=n2\frac{1}{4}(\pm(b-a)-2)\begin{cases}\frac{1}{4}(b-a-2)=\frac{1}{4}(4n)=n_{1}\\\frac{1}{4}(a-b-2)=\frac{1}{4}(4n)=n_{2}\end{cases}
aa 的值可通过遍历获得， b=Ca      C=4X−1b=\frac{C}{a}\;\;\;C=4X-1。

解题代码

由于a×b=Ca\times b=C，所以只需要遍历for(int a=1;a<=C_sqrt;i++)，其中 C_sqrt =C=\sqrt{C} 。
考虑 a,ba,b 的正负性，我们insert(a,b)和insert(-b,-a) 其中 a≤ba\le b。
实例代码使用set处理重复数字:
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
set<ll>solutions;
void func(ll a,ll b) 
{
	if(a>b)
		swap(a,b);
	if((a+b)%4==0) 
	{
		ll n1=(b-a-2)/4;
		ll n2=(a-b-2)/4;
		solutions.insert(n1);
		solutions.insert(n2);
	}
}
int main() 
{
	ll X;
	cin>>X;
	ll C=4*X-1;
	if(C==0)
		return 0;
	ll sqrt_C=sqrt(abs(C));
	for(ll i=1;i<=sqrt_C;i++) 
	{
		if(C%i==0) 
		{
			ll b=C/i;
			func(i,b);
			func(-b,-i);
		}
	}
	cout<<solutions.size()<<endl;
	for(ll q:solutions)
		cout<<q<<" ";
	return 0;
}
该程序时间复杂度约为 O(4X−1\sqrt{4X-1})。
完结撒花!

评论

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

正在加载评论...