考虑如下形式的二次丢番图方程：
x**2 – D*y**2 = 1
例如当 D=13时, x 的最小解是 649**2 – 13×180**2 = 1.
可以认为当D是平方数时方程无正整数解。
通过寻找当D = {2, 3, 5, 6, 7}时 x 的最小解，我们得到： 3**2 – 2×2**2 = 1 2**2 – 3×1**2 = 1 9**2 – 5×4**2 = 1 5**2 – 6×2**2 = 1 8**2 – 7×3**2 = 1
因此对于D ≤ 7, x 的最小解的最大值在D=5时取到。
找出D ≤ 1000中使得 x 的最小值取到最大的D的值。
参考：http://www.mathblog.dk/PRoject-euler-66-diophantine-equation/
x_max = 0D_res = 0for D in range(2, 1001): limit = int(pow(D, 0.5)) if limit * limit == D: continue m = 0 d = 1 a = limit numm1 = 1 num = a denm1 = 0 den = 1 while (num ** 2 - D * den ** 2 != 1): m = d * a - m d = (D - m * m) // d a = (limit + m) // d numm2 = numm1 numm1 = num denm2 = denm1 denm1 = den num = a * numm1 + numm2 den = a * denm1 + denm2 if num > x_max: x_max = num D_res = Dprint(D_res)新闻热点
疑难解答
