题解：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) ，容易得到二元一次方程组

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

#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;
}