题目链接:https://www.luogu.com.cn/problem/P1014
有理数可枚举
In 1873 Cantor proved the rational numbers countable, i.e. they may be placed in one-one correspondence with the natural numbers.
来自:Georg Ferdinand Ludwig Philipp Cantor
1873 年,Cantor 证明了有理数是可枚举的。可枚举指的是,你可以为集合中的每个元素都分配一个唯一的自然数,建立一个一一对应的关系。
有理数具有 \(p/q\) 的形式。\(p\) 表示分母,\(q\) 表示分子,其中 \(p\) 和 \(q\) 均为正整数。
我们可以将所有有理数排列在一个表格中,其中 \(p\) 表示行,\(q\) 表示列,
\[\begin{array}
{c|cccc}
p/q&1 &2 &3 &\cdots\\
\hline
1 &1/2&1/2&1/3&\cdots\\
2 &2/1&2/2&2/3&\cdots\\
3 &3/1&3/2&3/3&\cdots\\
\vdots&\vdots&\vdots&\vdots&\ddots\\
\end{array}
\]
为了对有理数进行编号,我们需要按照某种方式,将元素排成一条线。这里我们从 \(1/1\) 出发,然后移动到 \(2/1\),再往斜上方进行移动。继续按照这种方式,即,我们按照 \(\mathrm{Z}\) 型线路对沿路的元素进行编号,具体可查看下图,
图片来自:How can the set of the rational numbers be countable if there is no
通过上面的方式,我们为每个有理数都指定了一个编号,下表列出了一部分有理数和其编号,
\[\begin{array}
{c|ccc}
N &1 &2 &3 &4 &\cdots\\
\hline
R&1/1 &1/2 & 2/1 &3/1&\cdots\\
\end{array}
\]
通过编号 \(N\) 获取有理数 \(R\)
哪一条对角线?
题目中我们需要通过给定的编号 \(N\),来获取对应的有理数 \(R\)。
为了获取有理数 \(R\),我们首先需要知道 \(R\) 位于第几条对角线。通过观察图片,我们发现第一条对角线上的元素个数是 \(1\),第二条对角线上的元素个数是 \(2\),按照这种方式,我们可以得知第 \(n\) 条对角线上面的元素个数是 \(n\)。我们由此可以得知前 \(n\) 条对角线的元素个数总和为 \(1+2+\cdots+n\),根据求和公式我们可得,
\[1+2+\cdots+n=\sum_{i=1}^{n} i=\dfrac{n(n+1)}{2}
\]
假设编号 \(N\) 在 \(n\) 条对角线上,那么 \(N\) 满足以下的不等式
\[\begin{gather*}
\dfrac{n(n-1)}{2} < N \leqslant \dfrac{n(n+1)}{2} \\
n^2 - n < 2N \leqslant n^2+n \\
\\\hline\\
2N \leqslant n^2 + n \\
0 \leqslant n^2 + n - 2N \\
\dfrac{-1+\sqrt{1+8N}}{2} \leqslant n \\
\\\hline\\
n^2 - n < 2N \\
n^2 - n - 2N < 0 \\
n < \dfrac{1+\sqrt{1+8N}}{2} \\
\\\hline\\
\dfrac{-1+\sqrt{1+8N}}{2} \leqslant n < \dfrac{1+\sqrt{1+8N}}{2} \\
n \in \left[\dfrac{-1+\sqrt{1+8N}}{2}, \dfrac{1+\sqrt{1+8N}}{2}\right)
\end{gather*}
\]
我们注意到 \(\left[\dfrac{-1+\sqrt{1+8N}}{2}, \dfrac{1+\sqrt{1+8N}}{2}\right)\) 的区间长度为 1。这时候,我们考虑两种情况:
- 左端点为整数。右端点此时也为整数,所以我们可知 \(n\) 的值必为左端点,即 \(n = \left\lceil\dfrac{-1+\sqrt{1+8N}}{2}\right\rceil\)。如果为右端点减去一个极小值 \(\epsilon\),再对其向下取整,我们可以得到,\(n = \left\lfloor\dfrac{1+\sqrt{1+8N}}{2}-\epsilon\right\rfloor\);
左端点为小数。我们可以很容易就知道 \(n = \left\lceil\dfrac{-1+\sqrt{1+8N}}{2}\right\rceil\), 右端点此时也为小数,如果为右端点减去一个极小值 \(\epsilon\)(小于左端点和左端点向下取整的差值),再对其向下取整,我们可以得到,\(n = \left\lfloor\dfrac{1+\sqrt{1+8N}}{2}-\epsilon\right\rfloor\);
现在,我们已经得到了两个公式。通过任一公式,我们都可以知道元素位于第几条对角线。
对角线上第几个元素?
下一步,我们需要知道这个元素是对角线上的第几个元素。我们已经知道这个元素位于第 \(n\) 条对角线,那么只要将编号 \(N\) 减去前 \(n-1\) 对角线包含的元素个数,就可以得出元素在对角线 \(n\) 上的位置 \(k\)。结合求和公式,我们得到,
\[\begin{gather*}
k = N - \sum_{i=1}^{n-1} i \\
k = N - \dfrac{n(n-1)}{2}
\end{gather*}
\]
分母和分子
图片来自:How can the set of the rational numbers be countable if there is no
我们按照 \(\mathrm{Z}\) 型线路对沿路的元素进行编号,奇数对角线我们按照 \(\nearrow\) 的方向进行编号,偶数对角线我们则以 \(\swarrow\) 方向进行编号。
通过观察,我们发现同一对角线上的分母和分子之和 \(p+q\) 等于对角线编号 \(n+1\)。如果对角线方向为 \(\nearrow\),
则对角线上的第一个元素的分子为 \(1\),对角线上的第 \(k\) 个元素的分子为 \(k\);如果对角线方向为 \(\swarrow\),则对角线上的第一个元素的分母为 \(1\),对角线上的第 \(k\) 个元素的分母为 \(k\)。从而我们可以得到如下的公式,
\[p = \begin{cases}
(n+1)-k, & n \text{ 是奇数}\\
k , & n \text{ 是偶数}\\
\end{cases}
\]
\[q = \begin{cases}
(n+1)-k, & n \text{ 是偶数}\\
k , & n \text{ 是奇数}\\
\end{cases}
\]
代码
通过上面的公式,我们得到最终的代码,
// https://www.luogu.com.cn/problem/P1014
#include <iostream>
#include <cmath>
int main()
{
int N, n, k, p, q;
std::cin >> N;
n = ceil((sqrt(1+8*N)-1)/2);
/* Another way to calculate the diagonal number `n' */
// const double epsilon = 1e-9;
// n = floor((sqrt(1+8*N)+1)/2-epsilon);
k = N-n*(n-1)/2;
if (n&1)
{
p = (n+1) - k;
q = k;
}
else
{
p = k;
q = (n+1) - k;
}
std::cout << p << '/' << q << std::endl;
return 0;
}