分数排序
|
考虑形如$n/d$的分数，其中n和d均为正整数。若$n < d$且其最大公约数为1，则称该分数为最简真分数。
将所有$d\le 8$的最简真分数从小到大升序排列得
$$1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, \textbf{2/5}, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8$$
可以看出3/7的左边是2/5。
将所有$d\le 10^6$的最简真分数从小到大升序排列，求此时$3/7$左边的数的分子。
|
本题难度:
|
解答
|
所求的分数$n/d$即满足$n/d < 3/7$, $\gcd(n,d)=1$, $d\le 10^6$的最大分数。 双重循环遍历d和n,记录当前的最大值m，对每个d，搜索dm和$3d/7$之间的n并更新m即可。
如此得$428570/999997$, 因此结果是$428570$。
注：以下代码为Python3，因Python2中无math.gcd函数。(Python2中可以使用fractions.gcd)
import math
a,b=2,5
for d in range(9,1000001):
n=d*3//7
while n>d*a//b and math.gcd(d,n)>1:
n-=1
if n>d*a//b and math.gcd(d,n)==1:
a,b=n,d
print(a,b)
|
| |
