数学小记：1988IMOP6_随笔

数学小记：1988IMOP6

改编版 OI 题：给定 $n$，对满足 $(xy+1)\mid(x^2+y^2),x,y\in[1,n]$ 的 $(x,y)$ 计数，$n\le 10^{18}$。

对其分析，首先注意到 $xy,x^2,y^2$ 都是二次项，令 $x\le y$ 则可以推出 $x^2\le xy\le y^2$，则 $\frac{x^2+y^2}{xy+1}\approx \frac{y}{x}$。

这是初步的估计，接下来我们分析一下：

• $(xy+1)(\frac y x-1)=y^2-xy+\frac yx -1<y^2+x^2$。
• $(xy+1)(\frac y x+1)=y^2+xy+\frac y x+1> y^2+x^2$。

所以答案要么是 $\lfloor\frac y x\rfloor$ 要么是 $\lceil\frac y x\rceil$。

令 $y=qx+r$，若 $q$ 是 $\frac{x^2+y^2}{xy+1}$ 则 $r\in(-x,x)$，我们先讨论 $r=0$ 的特殊情况。

$$\begin{aligned}&\frac{x^2+(qx)^2}{x(qx)+1}=q \\&x^2+q^2x^2=q^2x^2+q \\&x^2=q,y=x^3 \end{aligned}$$

代入验证发现 $y=x^3$ 确实是一组特解。

讨论 $r>0$。

$$\begin{aligned}&\frac{x^2+(qx+r)^2}{x(qx+r)+1}=q \\&x^2+q^2x^2+2qxr+r^2=q^2x^2+qxr+q \\&x^2+r^2+qxr=q\end{aligned}$$

显然 $qxr\ge q,x^2+r^2+qxr>q$，该情况不成立。

讨论 $r<0$，另设 $y=qx-r,r\in(0,x)$。

$$\begin{aligned}&\frac{x^2+(qx-r)^2}{x(qx-r)+1}=q \\&x^2+q^2x^2-2qxr+r^2=q^2x^2-qxr+q \\&x^2+r^2=qxr+q \end{aligned}$$

看起来我们一筹莫展了，但是观察形式：$x^2+r^2=qxr+q=q(xr+1)$，我们由 $(x,y)$ 递归到了 $(x-y\bmod x,x)$。

而递归终止条件是我们推过的特解，$y=x^3$。

注意这个递归的形式十分苛刻，不仅要保证两参数的形式，还要保证 $\lceil\frac{y}{x}\rceil$ 是固定的值 $q$，它等于递归终点的 $x^2$。

因此我们会计数了，枚举递归终点，反向生成即可，$\log$ 层之内结束。