题目192：最优近似值
本帖最后由 永恒的蓝色梦想 于 2020-8-31 10:54 编辑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 1012, 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 不是完全平方数，找出界限为 1012 时， √n 的最优近似值的分母之和。
本帖最后由 guosl 于 2020-5-19 12:04 编辑
首先题目的翻译有致命错误！题目要求的是n的平方根的最佳逼近。
应用√n的连分数展开中分母最靠近 10^12的那个渐近分数。
但对分母最靠近 10^12的那个渐近分数的分母到10^12之间的验证没有好办法。{:10_250:} guosl 发表于 2020-5-18 08:50
应用n的连分数展开中分母最靠近 10^12的那个渐近分数。
大佬NP{:10_245:}
页:
[1]