Pell方程

#求解Pell方程y^2-Dx^2=1

from numpy import *
from math import *

D = int(input("请输入正整数D:"))
inter = int(floor(sqrt(D)))
#print(inter)

x1, x2 = 0, 1
x3 = (inter + x1) // x2
x4 = -(x1 - x2 * x3)

y02, y04 = x2, x4

y1, y2 = x4, (D - x4**2) / x2
y3 = (inter + y1) // y2
y4 = -(y1 - y2 * y3)

L = [x3, y3]

while abs(y02 - y2) > 0.1 or abs(y04 - y4) > 0.1:

    x1, x2, x3, x4 = y1, y2, y3, y4
    y1, y2 = x4, (D - x4**2) / x2
    y3 = (inter + y1) // y2
    y4 = -(y1 - y2 * y3)
    L.append(y3)

L.pop()

母1, 子1 = L[-1], 1
母2, 子2 = L[-2] * 母1 + 子1, 母1

print("Sqrt[D]的连分数形式为{}".format(L+[2*L[0]]))

for i in range(1, len(L) - 1):

    母1, 子1 = 母2, 子2
    母2, 子2 = L[-2 - i] * 母1 + 子1, 母1

if len(L) % 2 == 0:
    print("y={}".format(母2), "x={}".format(子2))
else:
    print("y={}".format(2 * 母2**2 + 1), "x={}".format(2 * 母2 * 子2))

上一篇：条件概率和独立性

下一篇：哈密顿-雅可比方程