本题乍看和第64题很相似，似乎只要求出$\sqrt n$的连分数表示就可以找出最优有理逼近数，但用题面中的数据尝试展开$\sqrt{13}$并观察分母可以发现5的下一项是33，因此第64题中的程序不能直接套用。
以下的解法使用法里序列的标准算法，这也是分母带上限的最优有理逼近问题的标准解法，最终结果是$57060635927998347$。
sq=set([i*i for i in range(2,317)])
bound=10**12
r=0
for n in range(2,100001):
if n not in sq:
a,b,c,d=0,1,1,0
while b+d <= bound:
if (a+c)*(a+c)-n*(b+d)*(b+d)>0:
c,d=a+c,b+d
else:
a,b=a+c,b+d
r+=b if 4*n*b*b*d*d < (a*d+b*c)*(a*d+b*c) else d
print r
|
