分数范围计数
|
考虑形如$n/d$的分数，其中n和d均为正整数。若$n < d$且其最大公约数为1，则称该分数为最简真分数。
把所有$d\le 8$的最简真分数从小到大排列得
$$1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, \textbf{3/8, 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$$
可以看出1/3和1/2之间共有3个元素。
把所有$d\le 12000$的最简真分数从小到大排列后1/3和1/2之间共有几个元素？
|
本题难度:
|
解答
|
策略与第71题相同，结果是$7295372$。
注：以下代码为Python3，因Python2中无math.gcd函数。(Python2中可以使用fractions.gcd)
import math
print(sum(math.gcd(d,n)==1 for d in range(2,12001) for n in range(d//3+1,d//2+1 if d%2 else d//2)))
|
| |
