Atcoder abc333

發表於 更新於 分類於 ， Disqus： 文章字數： 661 所需閱讀時間 ≈ 2 分鐘
G(连分数)

https://atcoder.jp/contests/abc333

G - Nearest Fraction

给一个(0,1)之间,不超过18位的小数r

求 一个分母<= N的最接近它的分数，如果有多个则输出最小的

n 1e10

2s

1024mb

我的思路

首先r肯定是通过字符串读取变成 整数/10的幂次

然后可以用 连分数的形式展开它

问题是这样的截断连分数因为分母<= N的限制 似乎直接截断不是最优的，二分最后一个位置的值？

例如样例$0.45, N = 5$

$\displaystyle 0.45=\frac{45}{100}=\frac{9}{20}=0+\frac{1}{\frac{20}{9}}=0+\frac{1}{2+\frac{1}{\frac{9}{2}}}=\frac{9}{20}=0+\frac{1}{\frac{20}{9}}=0+\frac{1}{2+\frac{1}{4+\frac{1}{2}}}$

这里 的 连分数是$[0,2,4,2]$

截断的话会是$\frac{1}{2},\frac{9}{4}$ 之间

而最优是$\frac{2}{5} = [0,2,2]$

所以想法是在会超过的地方 做个除法

然而 比较小数C++精度不够，用分数比较 longlong也会overflow

所以直接换语言，上python, 一次性过了

代码

https://atcoder.jp/contests/abc333/submissions/50068617

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
r=input()
N=int(input())

v = int(r[2:])
b = 10**(len(r)-2)
vv = v
bb = b
#  vv/bb

a = []
while b != 0:
    a.append(v//b)
    v%=b
    v,b = b,v

A = [[1,0],[0,1]]

def mul(A,B):
    C = [[0,0],[0,0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                C[i][j] += A[i][k]*B[k][j]
    return C

def sub_xy(X,Y):
    [x0,x1] = X # x0/x1 - y0/y1
    [y0,y1] = Y
    return [x0*y1-x1*y0,x1*y1]

def abs_x(X):
    return [abs(X[0]),X[1]]


for i in range(len(a)):
    ai = a[i]
    if ai*A[0][1]+A[1][1] <= N:
        A = mul([[ai,1],[1,0]],A)
    else:
        if N-A[1][1] > 0:
            [x0,y0] = A[0];
            ai = (N-A[1][1])//A[0][1];
            newA = mul([[ai,1],[1,0]],A)
            [x1,y1] = newA[0];
            # abs(x1/y1-vv/bb) - abs(x0/y0-vv/bb)
            res = sub_xy(abs_x(sub_xy([vv,bb],[x1,y1])),abs_x(sub_xy([vv,bb],[x0,y0])))
            # print(res)
            if res[0] < 0:
                A=newA #
            elif res[0] == 0:
                if sub_xy([x1,y1],[x0,y0])[0] <= 0:
                    A=newA
        break


print(f"{A[0][0]} {A[0][1]}");

总结

主要是之前做过project euler 066 这个题的时候,学过pell方程和连分数相关的数学知识，当时花了我 碎片的2个月时间反复的学，所以对连分数印象还很深的

这里用的性质就是，由连分数得到的渐近分数，其值是在分子或分母小于下一个渐近分数的分数中，最接近精确值的近似值。

//我看洛谷题解中有人说python甚至还有库，3行过G是吧

1
2
3
from fractions import Fraction # 引用
fr = Fraction(input())
print(*(fr - Fraction("1e-100")).limit_denominator(int(input())).as_integer_ratio())

然后 还有 Stern-Brocot 树， 也就是 每次 a/b,c/d 中间取(a+c)/(b+d), 且都是最简分数