数学 Math
题面
求一对正整数 $(x , y)$ 满足 : $x y + 1 | x^2 + y^2$ , $1 \le x \le y \le n$ .
解题思路
通过 Veta Jump ( 韦达跳跃 ) 可以发现 : $x^2 + y^2 = k(x y + 1)$ , 其中 $x < y$ . 则 $(y , k y - x)$ 也是一组解 , 从初解 $(x , x^3)$ 开始生成 , 总合法解数量为 $O(n^{\frac{1}{3}} \log n)$ . 不过不会 ╮(╯▽╰)╭ .
假设 $x$ 为主元 :
$$x^2 - k x y + y^2 - k = 0$$
易得 :
$$x_1 + x_2 = k y$$
当 $x_2 = kx - x$ 时是另一组解 , 同理可得另一组解 $kx - y$ .