071. 有序分数(Ordered fractions)

对于分数\(n/d\),其中\(n,d\)均为正整数,如果\(n<d\)且两者的最大公约数\(HCF(n,d)=1\),这个分数就称之为简分数。如果我们把\(d\le8\)的所有简分数以从小到大的顺序排列,则有:

$$ \frac{1}{8},\frac{1}{7},\frac{1}{6},\frac{1}{5},\frac{1}{4},\frac{2}{7},\frac{1}{3},\frac{3}{8},\frac{2}{5},\frac{3}{7},\frac{1}{2},\frac{4}{7},\frac{3}{5},\frac{5}{8},\frac{2}{3},\frac{5}{7},\frac{3}{4},\frac{4}{5},\frac{5}{6},\frac{6}{7},\frac{7}{8}, $$
可以看到,\(2/5\)是在\(3/7\)左边且紧邻它的分数。如果把\(d\le10^6\)的所有简分数以从小到大的顺序排列,那么在紧邻\(3/7\)且在它左边的分数的分子是多少?

分析:题目中所列的序列实际上就是数论中著名的Farey Sequence,关于这个序列的详细介绍可以参见这个维基页面Farey Sequence有一个有趣的性质,对于其中任意三个连续的分数,假设第一个分数为\(a/b\),第三个分数为\(c/d\),则中间第二个分数为\((a+b)/(c+d)\)。如在题目给出的示例中,\(1/7\)\(1/8\)\(1/6\)之间,而\((1+1)/(8+6)=2/14=1/7\)。类似的,我们可以验证序列中的其它分数也满足同样的性质。

题目要求紧邻\(3/7\)且在其左边的分数,则我们可以根据以上性质,先求出\(2/5\)\(3/7\)之间的分数等于\(5/12\),这个数距\(3/7\)\(2/5\)要更近。紧接着,我们可以求\(3/7\)\(5/12\)之间的数,为\(8/19\)。如此迭代下去,我们可以把这些分数列出来:

$$ \frac{2}{5},\frac{5}{12},\frac{8}{19},\frac{11}{26},\frac{14}{33},\cdots,\frac{2+3k}{5+7k} $$

题目中要求\(d\le10^6\),即要求\(5+7k\le10^6\),求得\(k=142856\),将其代入分子,则有:

$$ 2+3k=2+3\cdot142856=428570 $$

即为题目所求。显然这道题只需要笔算即可求解,以下代码只是以上思路的直接描述:

# time cost = 408 ns ± 1.89 ns

def main(D=10**6):
    k = int((D-5)/7)
    return 2+3*k