小数化分数的O(log2n)解法

具体约束:

给定一个小数x，x满足0<=x<1，且保证给定的x保留了18位小数

输出一个分数，使得分母不超过1e9，分子分母互质，且在满足这些条件的情况下最接近x

了解一下法雷数列和stern-brocot tree (某种意义上他们是在描述一个东西)

https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree

然后考虑在这个树上二分答案的上下界(个人觉得也可以叫伪二分)，

一层一层的下降，时间复杂度O(q), q为限制分母大小，本题中为1e9，不行

考虑加速，我们在一次二分过程结束后，上下界由 [l, r] 变为 [l, mid] 或 [mid, r]

但是实际上如果左边界一开始就非常贴近答案，那么我们连续下降很多次的过程中都是将 r 变为 (l + r) / 2

这样是很傻的，所以我们每次考虑下降多次，并且仍然满足条件即可

至于每次下降多少层，就二分一下就可以了

复杂度感觉不太直观，个人感觉是log^2(不负责猜测)，不然1w组数据，log的复杂度python不应该2s跑不出

python代码

 inf, inff = 10 ** 9, 10 ** 18

 for i in range(int(input())):

     n = int(input()[2:])

     if n == 0: print('0 1')

     else:

         lp, lq, rp, rq = 0, 1, 1, 1

         while max(lq, rq) <= inf:

             mp, mq = lp + rp, lq + rq

             if mp * inff <= mq * n:

                 l, r, mid, cnt = 1, (inf - lq) // rq + 1, -1, -1

                 while l <= r:

                     mid = l + r >> 1

                     if (lp + rp * mid) * inff <= (lq + rq * mid) * n:

                         cnt, l = mid, mid + 1

                     else:

                         r = mid - 1

                 lp, lq = lp + rp * cnt, lq + rq * cnt

             else:

                 l, r, mid, cnt = 1, (inf - rq) // lq + 1, -1, -1

                 while l <= r:

                     mid = l + r >> 1

                     if (rp + lp * mid) * inff > (rq + lq * mid) * n:

                         cnt, l = mid, mid + 1

                     else:

                         r = mid - 1

                 rp, rq = rp + lp * cnt, rq + lq * cnt

         if lq <= inf: print(lp, lq)

         else: print(rp, rq)

拓展应用:

问题:给定小数，求出分数p/q，满足p/q>x, q<=1e9,且p/q-x最小

解法:其实是同一个问题，同样是求上下界

问题: 给出abcd四个整数，保证a/b<c/d，求出pq两个整数，使得a/b<p/q<c/d且q最小

解法: 如果abs(ad - bc) == 1，那么a/b和c/d两个分数再某阶法雷序列里是相邻的，就有p=a+c, q=b+d

否则我们很容易有一个O(max(b,d))的做法，从上到下，求出两个分数每层的上下界

需要注意对a/b求的上下界是[l, r), 对c/d求的上下界是(l, r]

　　然后当某一层a/b的上界==c/d的下界的时候，这个分数就是p/q了

考虑一下这个东西同样是可以加速的，a/b的下界和c/d的上界我们是不关心的，加速方法同上

然后考虑加速a/b的上界r1和c/d的下界l2，我们非常关注他们第一次分开的时候

也就是最早满足r1 <= l2的时候，所以这个也是二分

至此我们就解决了这个问题，时间复杂度和上面是相同的！

巴特西

小数化分数的O(log2n)解法

最新文章

热门文章