【BZOJ 2852】强大的区间

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2852
神犇题解:http://blog.csdn.net/rzo_kqp_orz/article/details/52497951

解题报告

设最终区间包含的数为$t$
那么我们就是要求解这个不等式:$ka \le t \le kb$
我们分两种情况讨论:

1. $\lfloor a \rfloor \ne \lfloor b \rfloor$

这样的话,显然答案为$k = 1$

2. $\lfloor a \rfloor = \lfloor b \rfloor$

这样的话,我们先可以刨开$a,b$的整数部分
于是答案变为这个不等式的解:$s \cdot \frac{1}{b – \lfloor a \rfloor} \le k \le s \cdot \frac{1}{a – \lfloor a \rfloor}$

我们发现最后的式子与原问题形式相同,于是可以递归求解
更进一步,我们每次将较大的数减去较小的数,然后交换位置,这是典型的类欧几里得算法
于是我们就可以在:$O(\log n)$的时间复杂度内递归求解原问题了

至于代码,显然需要用高精度
但我不会py QwQ

3 thoughts to “【BZOJ 2852】强大的区间”

  1. It?¦s in point of fact a great and useful piece of information. I?¦m satisfied that you just shared this helpful info with us. Please keep us informed like this. Thanks for sharing.

Leave a Reply to oprolevorter Cancel reply

Your email address will not be published. Required fields are marked *