连分数求解pell方程

Pell 方程是形如 $x^2-dy^2=1$ 的二元二次方程，其中 $d$ 是正整数，$x$ 和 $y$ 是正整数。求解 Pell 方程的一种经典方法是使用连分数。下面是求解 Pell 方程的步骤：

1. 首先，我们找到 Pell 方程的一个基本解 $(x_0,y_0)$，可以通过暴力枚举或使用其他方法来找到基本解。

2. 我们使用基本解 $(x_0,y_0)$ 来构造一个无限循环小数：

$$\sqrt{d}=[a_0;\overline{a_1,a_2,\ldots,a_r,2a_0,\overline{a_1,a_2,\ldots,a_r,2a_0,\ldots}}]$$

其中，$a_0=\lfloor\sqrt{d}\rfloor$，$a_i$ 是循环节中的数字。

3. 我们将这个无限循环小数表示为一个连分数：

$$\sqrt{d}=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{\ldots+\frac{1}{2a_0+\frac{1}{a_1+\frac{1}{a_2+\ldots}}}}}}$$

4. 我们使用连分数的递归公式，计算出前 $n$ 个连分数的值：

$$\begin{aligned}&h_0=a_0, &k_0=1 \\ &h_1=a_0a_1+1, &k_1=a_1 \\ &h_i=a_ih_{i-1}+h_{i-2}, &k_i=a_ik_{i-1}+k_{i-2}\end{aligned}$$

其中，$h_i$ 和 $k_i$ 分别表示连分数的第 $i$ 个逼近分数的分子和分母。

5. 我们可以证明，对于任意 $n$，$(h_n,k_n)$ 都是 Pell 方程的解。这是由连分数的性质所决定的。

6. 最终，我们可以得到 Pell 方程的所有正整数解 $(x,y)$，它们可以通过 $(x,y)=(x_0h_n+dy_0k_n,x_0k_n+y_0h_n)$ 来计算。

需要注意的是，如果循环节长度为奇数，则最后一个连分数的分母应该是 $2a_0$，否则应该是 $1$。此外，如果循环节长度为 $0$，则 $a_1$ 应该等于 $2a_0$。