用python 3提交

from fractions import Fraction as F

def solve(a, b):
    G = int(a)
    a -= G
    b -= G
    if b >= 1:
        return 1, a.__ceil__() + G
    t, k = solve(1 / b, 1 / a)
    return k, t + G * k

a, b = map(F, input().split())
print(solve(a, b)[0])

不可二分，比如你试试0.45和0.55，它×2可以，×3不行。

连分数+高除高

标准解法

不过，题目描述似乎应将开区间改为闭区间

http://rpoi.5d6d.com/bbs.php

这里有解题报告

大家还是自己先做吧....

好久没人敢做这道题了……

还是讲讲思想吧：

其实并没有那么难

cgy4ever神牛的思想（足够了）+高精度

我的做法:

首先,整数部分无所谓的,只看小数部分. (当然a=3.9 b=4.1之类就直接出来了)

比如,求 a=0.2,b=0.3, a= 1 / 5 b= 1 / 3.3333..

5和3.3333..之间夹着一个(或多个)数,(最小的)是4,所以

4a=4/5 < 1 ,4b=4/3.3.. >1 ,那么4就是答案了.

如果说a=0.22 b=0.23 连分数展开 , a=1/4.347826.. b=1/4.54545...

4.347826和4.54545中间没有夹着数但我们可以根据前面的方法得到

2*4.347826=8.6956.. 和 2*4.54545=9.0909..之间夹着一个数,是9.

所以 a=2/8.6959.. b=2/9.0909.. , 9就是整个大问题的答案.

因为 a= 2*9 / 8.6959 > 2 b=2*9/9.0909 < 2.

而上述过程中涉及的子问题就是原问题.

这就得到了一个迭代的方法.

经过一些优化能变成非迭代的.

不过由于我写的高精度太差劲了所以TLE了.如果高精度写的好一些也许能AC吧~

等有足够多人AC的时候作者发一下标准答案吧,肯定又是强大的方法吧^^

郁闷这题不满足二分性质

靠编完程序调试才发现- -.3kb白写了郁闷

本来我还很高兴lg2(10^300)*300^2刚好过- -寒啊

感觉像升级版的 《神风堂人数》。

在curimit大牛的指点下，终于过了。

简单枚举是不行的，要用数学方法推导。

求K min ,使得[bk]-[ak]>=1.听别人说可以用二分

强大爆了。。。

果然够强大！0.0

Orz 宋神牛！

Orz curimit

Orz楼下众牛……

此题必须吃透方可......

我是沙茶

连分数啊= = 。。

123

哪位大牛知道为什么第10、11个点错？:

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 11：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：0ms