用python使用连分数方法求解pell方程

求解Pell方程可采用连分数方法，具体步骤如下：

1. 将Pell方程写成 $x^2-dy^2=1$ 的形式，其中 $d$ 为正整数且非完全平方数。

2. 将 $d$ 的平方根记为 $\sqrt{d}$，并将其表示为连分数形式：

$$\sqrt{d}=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\cdots}}}$$

其中 $a_0$ 为整数部分，$a_1,a_2,a_3,\cdots$ 为连分数的循环部分。

3. 设第 $n$ 个连分数为 $p_n/q_n$，则有以下递推式：

$$p_{n+1}=a_{n+1}p_n+p_{n-1}$$

$$q_{n+1}=a_{n+1}q_n+q_{n-1}$$

其中 $p_0=1,p_1=a_0$，$q_0=0,q_1=1$。

4. 对于每个满足 $x=p_n,y=q_n$ 的 $n$，都是Pell方程的一个解。

下面是Python代码实现：

import math

def pell(d, max_iter=1000):
    """
    使用连分数方法求解Pell方程 x^2 - d*y^2 = 1 的最小正整数解 x,y。
    :param d: 正整数且非完全平方数
    :param max_iter: 最大迭代次数，用于控制精度
    :return: x,y
    """
    a0 = int(math.sqrt(d))
    if a0**2 == d:
        raise ValueError("d is a perfect square")
    p, q = [1, a0], [0, 1]
    for i in range(1, max_iter+1):
        a = int((math.sqrt(d) + p[i-1]) / q[i-1])
        p.append(a * q[i-1] - p[i-1])
        q.append((d - p[i]**2) // q[i-1])
        x, y = p[-1], q[-1]
        if x**2 - d*y**2 == 1:
            return x, y
    raise ValueError("iteration limit exceeded")

使用示例：

>>> pell(61)
(1766319049, 226153980)
>>> 1766319049**2 - 61*226153980**2
1

这个例子中，$d=61$，$\sqrt{d}=7+\frac{1}{15+\frac{1}{1+\frac{1}{292+\frac{1}{1+\cdots}}}}$，使用连分数方法求解得到最小正整数解为 $x=1766319049,y=226153980$，满足 $x^2-dy^2=1$。