12.分数计数

考虑形如 $n / d$ 的分数, 其中 $n$ 和 $d$ 均为正整数。如果 $n<d$ 且其最大公约数为 1 , 则称该分数为最简真分数。

将所有 $d \leq 8$ 的最简真分数构成的集合按大小升序排列: \(\begin{gathered} 1 / 8,1 / 7,1 / 6,1 / 5,1 / 4,2 / 7,1 / 3,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 \end{gathered}\)

可以看出该集合中共有 21 个元素。 所有 $d \leq 1,000,000$ 的最简真分数构成的集合中共有多少个元素?

Answer: 303963552391