题目链接：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\) 表示列，
为了对有理数进行编号，我们需要按照某种方式，将元素排成一条线。这里我们从 \(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\)，根据求和公式我们可得，
假设编号 \(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\)。从而我们可以得到如下的公式，
代码
通过上面的公式，我们得到最终的代码，
// 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;
}