AquaRio 的博客

AquaRio 的博客

题解 P5596 【【XR-4】题】

posted on 2019-10-20 22:47:17 | under 题解 |

更好的阅读体验

题目传送门: [XR-4] 题

Description

给出自然数 $a,b$ 求满足下列条件的自然数对 $(x,y)$ 的个数:

$$y^2 - x^2 = ax + b$$

Solution

这是一道好题,好在我考试的时候想了很久

我们就来梳理一下这题的思路。

  • Subtask 1:

这个3pts估计人人都会吧。

if(a==b&&a==0){
    puts("inf");
    return 0;
}
  • Subtask 2:

打表打表!6pts到手!

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})$ 。

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$$

我们发现当左边也是一个完全平方式子时,它有无穷多解。感性理解一下,只有这一种情况。

于是我们又前进了一大步

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

/*
    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;
}