题解 P5596 【【XR-4】题】

[题目链接]( https://www.luogu.org/problem/P5596 ) 说一个不一样的方法，来自[Mr_Wu]( https://www.luogu.org/space/show?uid=62308 ) 由 $y^{2}-x^{2}=ax+b(a,b,x,y\in N)$, 变形可得$x^{2}+ax+b=y^{2}$. 显然，$x^{2}+ax+b$是完全平方数 此时构造式子$x^{2}+2px+p^{2}(p\in N)$，使得$p$是满足$2p\le a$且$p^{2}\le b$的数中最大的。 显然，$\forall x\in N,x^{2}+2px+p^{2}\le x^{2}+ax+b$. 同理，构造式子$x^{2}+2qx+q^{2}(q\in N)$，使得$q$是满足$2q\ge a$且$q^{2}\ge b$的数中最小的。 显然，$\forall x\in N,x^{2}+2qx+q^{2}\ge x^{2}+ax+b$. 设$y^2=(x+r)^2$，即$x^{2}+ax+b=(x+r)^2$ $\because$ $(x+p)^2\le(x+r)^2\le(x+q)^2$ $\therefore p\le r\le q$ 此时$x=\frac{r^2-b}{a-2r}$ 又因为$x$为整数，所以只需要解出所有$r$对应的$x$，判断其是否是整数，如果是，就是合法解。 值得注意的是，如果$x^{2}+ax+b$是完全平方式，输出inf即可。