洛谷5596 【XR-4】题

题解 数学 尚无评定
题目链接 编辑文章

题意

题解

$\because a,b\geq 0 \ , \ \therefore y\geq x$ ,不妨设 $y=x+k(k\geq 0)$ ,原式化为:

$$k^2+2kx=ax+b\tag{1}$$

当 $a=2k,b=k^2$ ,即 $a^2=4b$ 时有无数组解,输出 inf

否则 $(1)$ 式可以化为:

$$(a-2k)x=k^2-b$$

$$x=\dfrac{k^2-b}{a-2k}$$

枚举 $k\in [0,\max(\sqrt{b},\frac{a}{2})]$ ,再校验 $x$ 是否为整数即可。

#include<bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

ll a,b;

signed main()
{
    a=read(); b=read();
    if (a*a==4*b) return 0&puts("inf");
    ll maxk=max((ll)sqrt(b),a>>1),ans=0;
    for (ll k=0;k<=maxk;k++)
    {
        ld x=(ld)(k*k-b)/(ld)(a-2*k);
        if (x>=0 && x==(ll)x) ans++;
    }
    return !printf("%lld",ans);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空