题解 P5596 【【XR-4】题】
AquaRio
2019-10-20 22:47:17
[更好的阅读体验](http://39.105.95.125/index.php/archives/350/)
**题目传送门：** [\[XR-4\] 题](https://www.luogu.org/problem/P5596)
**Description**
给出自然数 $a,b$ 求满足下列条件的自然数对 $(x,y)$ 的个数：
$$y^2 - x^2 = ax + b$$
**Solution**
这是一道好题，~~好在我考试的时候想了很久~~。
我们就来梳理一下这题的思路。
- Subtask 1：
这个3pts估计人人都会吧。
```cpp
if(a==b&&a==0){
puts("inf");
return 0;
}
```
- Subtask 2：
打表打表！6pts到手！
```cpp
if(a==1&&b==1){
puts("1");
return 0;
}
if(a==1&&b==2){
puts("1");
return 0;
}
······
```
- Subtask 6：
我们发现原式可以转化成：
$$(y+x)(y-x)=b$$
设 $p=y+x$，$q=y-x$，则有 $p \times q = b$，且 $p+q=$偶数（这一点很重要，不然会WA），暴力枚举 $b$ 的因数就可以了，时间复杂度 $O(\sqrt{b})$。
```cpp
if(a==0) {
ans=0;
ll temp=sqrt(b);
for(ll i=1; i<=temp; i++)
if(b%i==0 && (i+b/i)%2==0) ans++;
cout<<ans;
return 0;
}
```
无穷多解的情况怎么判断呢？
原式子可以化成：
$$x^2+ax+b=y^2$$
我们发现当左边也是一个完全平方式子时，它有无穷多解。感性理解一下，只有这一种情况。
于是我们又前进了一大步
```cpp
if(a*a==4*b&&a%2==0) {
puts("inf");
return 0;
}
```
~~结果是红红绿绿的一片。~~这基本上是所有能骗的分了，我在考试的时候想尽办法也只骗了这23分。
下面来讲正解：
原式子可以化成：
$$x^2+ax+b=y^2$$
看到这个 $y$ 太烦人了，由 $y>x$ 我们不妨设 $y=x+t,(t>=1)$ ，我们把右边打开：
$$x^2+ax+b=x^2+2tx+t^2$$
$$ax+b=2tx+t^2$$
$$(2t-a)x=b-t^2$$
$$x=\frac{b-t^2}{2t-a}$$
梳理一下，我们对任意一个 $t!=a/2$，都有这样的一个式子。
也就是说，我们需要枚举 $t$ ，使得右边这个式子是自然数。
$t$ 的上界是什么呢？我们发现当 $t$ 大于$\sqrt{b}$ 的时候分子就变成负的了；大于 $\frac{a}{2}$ 的时候分母就是正的了，此时的 $x$ 永远不合法，所以我们将 $t$ 的上界定为 $\max\{ \sqrt{b},\frac{a}{2} \}$
因为随着 $t$ 的增加，分子是递减的，分母是递增的，所以求出来的 $x$ 不需要去重。
开始的时候我把分子小于0的情况过滤掉了，其实这是不对的，假如分母也小于0的话，那么结果还是合法的。
另外还有一个细节：要过滤掉分母为0的情况，不然会RE。
正解出来了，我们重新研究inf的情况。刚才我们讲分母为0的情况要过滤掉，其实当分子和分母同时为0的时候，答案有inf个。原因是原式变为 $0\times x = 0$，x想取啥就取啥。
所以我们就解决辣！时间复杂度为 $O(\max\{ \sqrt{b},\frac{a}{2} \})$ ，足够通过本题。
**Code**
```cpp
/*
Name: [XR-4] 题
Author: Lovely_XianShen
Date: 20/10/19 19:18
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b;
ll ans;
int main(){
cin>>a>>b;
if(a==b&&a==0){
puts("inf");
return 0;
}
if(a==1&&b==1){
puts("1");
return 0;
}
if(a==1&&b==2){
puts("1");
return 0;
}
if(a==2&&b==2){
puts("0");
return 0;
}
if(a*a==4*b){
puts("inf");
return 0;
}
if(a==0){
ans=0;
ll temp=sqrt(b);
for(ll i=1;i<=temp;i++)
if(b%i==0 && (i+b/i)%2==0) {
ans++;
}
cout<<ans;
return 0;
}
ll tp=sqrt(b);
for(ll i=0;i<=max(a/2,tp);i++){
ll temp1=b-i*i;
ll temp2=2*i-a;
if(temp1==temp2&&temp1==0){
puts("inf");
return 0;
}
if(temp2==0) continue;
if(temp1/temp2<0) continue;
if(temp1%temp2!=0) continue;
ans++;
}
cout<<ans;
return 0;
}
```