洛谷 P1014：Cantor 表

【题目来源】
https://www.luogu.com.cn/problem/P1014
https://www.acwing.com/problem/content/5510/

【题目描述】
现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。
他是用下面这一张表来证明这一命题的：

1/1  1/2  1/3  1/4  1/5  …
2/1  2/2  2/3  2/4  …
3/1  3/2  3/3  …
4/1  4/2  …
5/1  …
…

我们以 Z 字形（参考下图）给上表的每一项编号，第一项是 1/1，然后是 1/2，2/1，3/1，2/2，…

【输入格式】
输入一个整数 N。

【输出格式】
输出表中的第 N 项。

【输入样例】
7

【输出样例】
1/4

【数据范围】
1≤N≤10^7

【算法分析】
● 首先将 Z 字形的 Cantor 表拉伸为线性。

通过观察线性的 Cantor 表，会发现第 i 段有 i 个“分母+分子”的和为 i+1 的分数。这是本题代码编写的重要出发点。
● 由于本题有 10^7 个数据，并依据上文所言“第 i 段有 i 个‘分母+分子’的和为 i+1 的分数”的结论，可设所有数据分为 x 段。其中，x 满足 1+2+3+……+x=10^7，等价于 x(x+1)/2=10^7，即 x 约取到 10^4，也即所有数据约划分为 10^4 段。
●​​​​​​​ 输出是分数的形式，所以需要以字符的形式输出除号。同时一定要注意偶数段、奇数段各个分数的形式。

【算法代码】

#include <bits/stdc++.h>
using namespace std;int cnt=0;
int main() {int n;cin>>n;for(int i=1; i<=10000; i++) {for(int j=i; j>=1; j--) {cnt++;if(cnt==n && i%2!=0) cout<<j<<"/"<<(i+1-j)<<endl;else if(cnt==n && i%2==0) cout<<(i+1-j)<<"/"<<j<<endl;}}return 0;
}/*
in:7
out:1/4
*/

 另外，一个更值得推荐的精妙写法如下所示：

#include <bits/stdc++.h>
using namespace std;int main() {int i,n;cin>>n;for(i=1; i<n; i++) n-=i;if(i%2!=0) cout<<i+1-n<<"/"<<n;else cout<<n<<"/"<<i+1-n;return 0;
}/*
in:7
out:1/4
*/

这个精妙写法，首先利用 for(i=1; i<n; i++) n-=i; 确定第 n 个元素是第几块儿中的第几个元素。然后利用块儿的奇偶性及第 i 块儿中元素的分母分子之和为 i+1 的性质进行输出。（注意：分块儿规则是第 i 块儿有 i 个元素）





【参考文献】
https://www.luogu.com.cn/problem/solution/P1014
https://www.acwing.com/solution/content/231311/