题解 P5596 【【XR-4】题】

一叶知秋。 · 2019-10-21 07:58:29 · 题解

首先，看看式子：

移项，再等式两边同乘4，得：

然后配方，得：

由题意，得：y^2+a^2-4b必须为完全平方数

令z^2=4y^2+a^2-4b

移项，再因式分解，得：

所以找a^2-4b的因子即可

然后还有条件：

倘若a^2-4b=uv(u<v)（等于可以不考虑，因为肯定不可行）

则u，v为所求当且仅当：

1、u，v同奇偶

2、4|(v-u)

3、求出的y，z不能为负

4、z与a同奇偶

然后这道题就做完了。。。

代码如下：

#include<cstdio>
#include<cstring>

#define maxn 1111111

inline long long read(){
    long long r=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')r=(r<<1)+(r<<3)+(c^48),c=getchar();
    return r*f;
}

inline long long abs(long long x){
    return x<0?-x:x;
}

long long a,b,u,v,x,ans;

int main(){
    a=read(),b=read();
    if(!(a*a-4*b))return printf("inf"),0;
    x=a*a-4*b;
    for(long long i=(a+1)%2+1;i*i<=abs(x);i+=2){//要满足z与a同奇偶
        if(x%i)continue;
        u=i,v=abs(x/i);
        if(x<0)u=-u;//倘若为负，应该让u为负，证明不难
        if((v-u)%4)continue;//要能被4整除
        if(v-(v-u)/2<a)break;//求出来是负数了，后面肯定求出来的越来越小
        ans++;
    }
    printf("%lld",ans);
    return 0;
}