题解

29 条题解

  • 2
    @ 2020-06-28 19:52:21

    用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
    @ 2016-09-09 22:41:27

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

  • 0
    @ 2009-04-29 10:36:08

    连分数+高除高

    标准解法

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

  • 0
    @ 2009-03-11 16:51:29

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

    这里有解题报告

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

  • 0
    @ 2009-02-14 20:32:34

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

    还是讲讲思想吧:

    其实并没有那么难

    cgy4ever神牛的思想(足够了)+高精度

  • 0
    @ 2009-02-01 19:20:21

    我的做法:

    首先,整数部分无所谓的,只看小数部分. (当然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的时候作者发一下标准答案吧,肯定又是强大的方法吧^^

  • 0
    @ 2009-01-31 21:10:47

    郁闷这题不满足二分性质

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

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

  • 0
    @ 2009-01-31 00:36:22

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

  • 0
    @ 2009-01-30 15:54:54

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

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

  • 0
    @ 2009-01-23 19:23:33

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

  • -1
    @ 2014-11-07 23:09:09

    强大爆了。。。

  • -1
    @ 2013-10-31 15:25:06

    果然够强大!0.0

  • -1
    @ 2009-07-19 21:51:23

    Orz 宋神牛!

  • -1
    @ 2009-07-17 21:00:38

    Orz curimit

  • -1
    @ 2009-07-11 12:22:38

    Orz楼下众牛……

  • -1
    @ 2009-06-26 17:24:37

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

  • -1
    @ 2009-07-13 08:04:04

    我是沙茶

  • -1
    @ 2009-05-26 15:14:44

    连分数啊= = 。。

  • -1
    @ 2009-04-22 23:07:31

    123

  • -1
    @ 2009-02-03 06:36:10

    哪位大牛知道为什么第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

信息

ID
1504
难度
8
分类
数论 | 高精度 点击显示
标签
递交数
193
已通过
23
通过率
12%
上传者