连分数求解pell方程

Pell方程是指形如 $x^2 - ny^2 = 1$ 的二次不定方程，其中 $n$ 是正整数且 $n$ 不是完全平方数。求解Pell方程的一个重要方法是将其转化为连分数形式。

设 $x_0$ 和 $y_0$ 是Pell方程的一组最小正整数解，那么可以将 $x_0 / y_0$ 的连分数表示写成如下形式：

$$
\frac{x_0}{y_0} = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \cdots}}}
$$

其中 $a_0$ 是 $x_0 / y_0$ 的整数部分，$a_1, a_2, a_3, \cdots$ 是其连分数的部分分数项。如果将上式左右两边同时乘以 $y_0$，则得到：

$$
x_0 = a_0 y_0 + y_1
$$

其中 $y_1 = y_0 / (a_1 + (y_0 \mod a_1))$，即将 $y_0$ 沿着 $a_1$ 的余数部分分解。同理，可以得到 $x_1, y_2, x_2, y_3, \cdots$ 的递推公式：

$$
\begin{aligned}
x_{i+1} &= a_{i+1} y_i + y_{i+1} \\
y_{i+1} &= \frac{y_i}{a_{i+1} + (y_i \mod a_{i+1})}
\end{aligned}
$$

对于Pell方程 $x^2 - ny^2 = 1$，其解可以通过不断计算连分数的递推公式来得到。设 $x_0 = 1, y_0 = 0$，则有：

$$
\begin{aligned}
a_0 &= \lfloor \sqrt{n} \rfloor \\
x_1 &= a_0 \\
y_1 &= 1 \\
a_1 &= \lfloor \frac{a_0 + x_1}{y_1} \rfloor \\
x_2 &= a_1 x_1 + x_0 \\
y_2 &= a_1 y_1 + y_0 \\
a_2 &= \lfloor \frac{a_0 + x_2}{y_2} \rfloor \\
x_3 &= a_2 x_2 + x_1 \\
y_3 &= a_2 y_2 + y_1 \\
a_3 &= \lfloor \frac{a_0 + x_3}{y_3} \rfloor \\
\cdots
\end{aligned}
$$

其中 $\lfloor x \rfloor$ 表示不大于 $x$ 的最大整数。直到某一步出现 $x_i^2 - ny_i^2 = 1$ 的情况，此时 $x_i$ 和 $y_i$ 就是Pell方程的一组正整数解。