Vieta Jumping
顾名思义，这是一种结合 Vieta Theorem 即韦达定理的解题方式，通常用于数论，在 OI 中好像没啥应用，但是总有些无良出题人把 IMO 或者 TST 改成 OI 题。
我们会主要会使用韦达定理和无穷递降法。
简单来说，无穷递降法是假设存在解 $x$，我们论证可以从 $x$ 推出更小的解 $x'$，这与存在最小解矛盾，从而说明了这种递减操作不存在，以此说明原命题成立。
而 Vieta Jumping 就是在「推出更小的解」这一步上运用韦达定理。
IMO 1988 P6
$$
k=\frac{a^2+b^2}{ab+1}\in\mathbb{Z^+}
$$证明：$k$ 是完全平方数。
考虑固定一个非完全平方数 $k$。
对于方程：
$$
\begin{equation}
\dfrac{a^2+b^2}{ab+1}=k\label{a}
\end{equation}
$$
假如有解，考虑取出 $a+b$ 最小的解 $(a,b)$，不妨设 $a<b$（不难发现若 $a=b$，则 $2a^2=ka^2+1$，有 $a=b=k=1$，$k$ 是完全平方数，与假设矛盾，故 $a\ne b$），于是有：
$$
b^2-kab+a^2-k=0
$$
所以 $b$ 是方程 $x^2-kax+a^2-k=0$ 的一根，根据韦达定理，有：
$$
\begin{cases}
b+b'=ka\\
bb'=a^2-k
\end{cases}
$$
于是 $b'=ka-b$，容易证明 $b’$ 是正整数，$(a,b')$ 也是 $\eqref{a}$ 的解，由于最小解的假设，有 $b'>b$。
$$
b'=\frac{a^2-k}{b}<\frac{a^2}{b}<b
$$
矛盾，故 $k$ 是完全平方数。$\blacksquare$
改编（学数学）
Description
给定 $n$，求满足 $ab+1\mid a^2+b^2,1\le a\le b\le n$ 的正整数对 $(a,b)$ 对数。
多组询问。
$n\le10^{18}$
Solution
与上面方法是一样的。
我们已经知道 $k$ 是完全平方数了，并且，对于某个 $k$ 如果有解 $(a,b)$，我们知道 $(a,ka-b)$ 也是一组解，注意这里 $ka-b=\dfrac{a^2-k}{b}<\dfrac{a^2}{b}\le a$，所以准确来说应该把这一组新的解写成 $(ka-b,a)$。
这个无穷递降的过程会在 $ka-b=0$ 时结束（无穷递降的过程不可能不经过 0，否则存在一个时刻 $a,b$ 异号，$k$ 是负数或不存在），若 $k=x^2$，则此时 $a=x,b=x^3$，所以我们可以确定对于每个 $k$ 的最小解，反向递推即可得到所有解，解数很少，将所有值域范围内的答案存下来，每次查询二分即可。
代码很简单，略去。
USA TST 2002 P6
求
$$
\frac{a^2+b^2}{ab-1}\in\mathbb{Z^+},a\le b
$$
的所有解。
看起来和上面一题一模一样，但也完全不一样。
首先我们令 $a=1$，此时即要求 $\dfrac{b^2+1}{b-1}\in\mathbb{Z^+}$ 的所有解，变形得 $b+1-\dfrac{2}{b-1}$，所以只需 $b-1\mid 2$，又 $b$ 是正整数，故 $b=2\text{ or }3$。
接下来，类似的，考虑：
$$
\begin{equation}
\frac{a^2+b^2}{ab-1}=k,k\in\mathbb{Z^+}\label{b}
\end{equation}
$$
固定 $k$，整理得：
$$
\begin{equation}
a^2-kba+b^2+k=0
\end{equation}
$$
假设存在解 $(a,b)$，类似的有：
$$
\begin{cases}
a+a'=kb\\
aa'=b^2+k
\end{cases}
$$
$(a',b)$ 也是 $\eqref{b}$ 的解，并且 $a'=\dfrac{b^2+k}{a}>\dfrac{b^2}{a}\ge b$，所以准确来说应该调整两个数的顺序为 $(b,a')$。
这是一个递增的递推过程，我们可以将其反向，也就是将 $(a,b)\to(b,kb-a)$ 改写为 $(a,b)\to(ka-b,a)$，这递推式最终会落入一个循环，例如 $(1,2)\leftrightarrow(1,3)$。
最小的两个解形如 $(a,b)$ 和 $(a,ka-b)$，于是对于最小解 $(a_0,b_0)$，一定有 $2b_0\le ka_0$，结合 $b_0\ge a_0$，我们可以使用图像来对解的情况进行分析。
这是 $k=5$ 时的图像：
可以找到满足条件的最小解 $(1,2)$。
然后我们也可以画出其余 $k$ 值对应的图像，发现其余情况均不存在。正确性肯定是有的，但可能还是有些偏感性。
于是 $k$ 只能是 $5$，从 $(1,2)$ 和 $(1,3)$ 开始递推就可以得到所有解。
还有一些 Math SE 上的内容可供参考：Is it true that $f(x,y)=\dfrac{x^2+y^2}{xy-t}$ has finitely many distinct positive integer values with $x,y$ positive integers?
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
