对角枚举

您当然知道整数集和有理数集之间等价性的这个很好的证明。

我们考虑一个用整数水平和垂直编号的无限网格：

我们根据上面的模式遍历这个网格并计算每一对 (i,j)，其中 i 和 j 是互质的。

我们得到以下双射：

1 - $\frac{1}{1}=1$

2 - $\frac{1}{2}$
3 - $\frac{2}{1}=2$

4 - $\frac{3}{1}=3$
5 - $\frac{1}{3}$

6 - $\frac{1}{4}$
7 - $\frac{2}{3}$
8 - $\frac{3}{2}$
9 - $\frac{4}{3}$

10 - $\frac{5}{1}=5$
11 - $\frac{1}{5}$

12 - $\frac{1}{6}$
13 - $\frac{2}{5}$
14 - $\frac{3}{4}$
15 - $\frac{4}{1}=4$
16 - $\frac{5}{2}$
17 - $\frac{6}{1}=6$

如果我们遍历 $6\times 6$ 网格的上对角矩阵，我们就会得到 17 有理数。

在 ${10}^9\times {10}^9$ 网格的上对角矩阵中我们可以算出多少个有理数？

您将获得： 303964542391 对应 ${10}^6\times {10}^6$ 网格
[我的时间：< 90 秒]