考慮如下形式的二次丟番圖方程：
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)新聞熱點
疑難解答
