题目192：最优近似值

欧拉计划

Best Approximations

Let x be a real number.
A best approximation to x for the denominator bound d is a rational number r/s in reduced form, with s ≤ d, such that any rational number which is closer to x than r/s has a denominator larger than d:

|p/q-x| < |r/s-x| -> q>d

For example, the best approximation to √13 for the denominator bound 20 is 18/5 and the best approximation to √13 for the denominator bound 30 is 101/28.

Find the sum of all denominators of the best approximations to √n for the denominator bound 10¹², where n is not a perfect square and 1 < n ≤ 100000.

题目：

定义 x 为一个实数。

对应于分母界限 d，x 的最优近似值（另一题翻译成了最佳逼近）为 r/s，其中 s  ≤  d，并且是最简形式。也就是说，任何一个比 r/s 更接近 x 的有理数，它的分母一定比 d 大：

|p/q-x| < |r/s-x| -> q>d

比如，如果界限为 20 的话，√13 的最优近似值是 18/5，而界限为 30 时，则是 101/28。

对于1 < n ≤ 100000，且 n 不是完全平方数，找出界限为 10¹² 时， √n 的最优近似值的分母之和。

guosl

首先题目的翻译有致命错误！题目要求的是n的平方根的最佳逼近。
应用√n的连分数展开中分母最靠近 10^12的那个渐近分数。

但对分母最靠近 10^12的那个渐近分数的分母到10^12之间的验证没有好办法。

永恒的蓝色梦想

guosl 发表于 2020-5-18 08:50
应用n的连分数展开中分母最靠近 10^12的那个渐近分数。

大佬NP