题解：P11701 [ROIR 2025] 平方差

提供一种好想的 $O(\sqrt{d}) 做法

第一眼看到

1\le l \le r \le 10^{18}

，~~还以为暴力就能直接过~~，于是写了个

O(\sqrt{r})

枚举，毫无疑问地 TLE 了（悲）

于是我开始尝试推式子，并重点关注较小的

d

我们知道

x^2-y^2

可以转化为

(x+y)(x-y)

又因为

x

、

y

均为正整数，且

x \ge y

（结合

d \ge 1

，实际上应为

x>y

)
所以

x+y

、

x-y

也应为正整数，且

x+y

更大

回到本题，由于满足

x^2-y^2=d

，因此同样满足

(x+y)(x-y)=d

，不妨记

i=x+y

、

j=x-y

，则等式化为

ij=d

，结合上述内容（

i

、

j

为正整数），则可以通过枚举合法的

(i,j)

数对来尝试求解（假定

i<j

）

对于合法的

(i,j)

，容易得到二元一次方程组

\begin{cases} x+y=j\\ x-y=i \end{cases}

从而解得

x=(i+j)/2

、

y=x-i

结合

x

、

y

都是正整数的限制，该方程组要么无解、要么有一对解，是否无解取决于

i+j

是否是

2

的倍数。

那么本题就做完了，枚举

d

的因子对

(i,j)

，随后验证是否有解即可（别忘了

x

和

y

的范围）

代码很短，码风很丑QwQ

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int l,r,d,ans;
signed main()
{
	cin>>d>>l>>r;
	for(int i=1;i<=sqrt(d);i++)  //枚举d较小的因子i
	{
		if(d%i) continue;  //i不是d的因子
		int j=d/i;  //d较大的因子j
		if(i+j&1) continue;  //i+j不是2的倍数
		int x=i+j>>1;  //计算x
		if(x*x<l||x*x>r) continue;  //x不在范围内
		int y=x-i;  //计算y
		if(y*y<l||y*y>r) continue;  //y不在范围内
		ans++;  //排除所有错误后，计算答案
	}
	cout<<ans;
}

题解：P11701 [ROIR 2025] 平方差

文章操作

提供一种好想的 $O(\sqrt{d}) 做法

相关推荐

评论

题解：P11701 [ROIR 2025] 平方差