P5596 【XR-4】题
这道题目在考场上推了很长一段时间,还推错了好几次,最后终于推出来了却死在边界情况上。
下面我们来推一下应该怎样去解决这道题目。
[y^{2}-x^{2}=a x+b
]
[y^{2}=x^{2}+ax+b
]
[ecause xge0 , a ge 0 ,b ge 0
]
[ herefore y^2ge x^{2}+ax+b
]
[ herefore 我们设 y=x+i (i ge 0)
]
[ecause y^2=(x+i)^2=x^2+2ix+i^2 ,y^2=x^{2}+ax+b
]
[ herefore x^2+2ix+i^2=x^{2}+ax+b
]
[(2i-a)x=b-i^2
]
[x=frac{b-i^2}{2i-a}
]
[ecause xge 0
]
[ herefore 2i-a|b-i^2 ,就是(b-i^2)\%(2i-a)==0
]
所以我们直接枚举 (i) 看是否满足条件就可以了,还有特判一下分母为 (0) 的合法情况。
不过需要考虑的还有枚举上界。
我们发现当 (i>sqrt b) 时,分子为负数 , (i>frac{a}{2}) 时,分母为正数,这样就永远无法满足要求,因为分子会不断减小,分母会不断增大,但是也有可能分母和分子都是负数且满足上面的式子,所以我们要取 (max(sqrt b,frac{a}{2})) 。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b;
ll sum;
int main()
{
scanf("%lld%lld",&a,&b);
for (ll i=0;i<=max((ll)sqrt(b),a/2);i++)
{
ll now1=b-i*i,now2=2*i-a;
if (now1==0&&now2==0)
{
printf("inf
");
return 0;
}
if ((now1>0&&now2>0)||(now1<0&&now2<0)||now1==0)
if (now1%now2==0) sum++;
}
printf("%lld
",sum);
return 0;
}
还有就是如果一种判边界的情况不正确,我们可以试一下另一种方法。