P1014 [NOIP 1999 普及组] Cantor 表

P1014 [NOIP 1999 普及组] Cantor 表

题目描述

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

我们以 Z 字形给上表的每一项编号。第一项是 $1/1$，然后是 $1/2$，$2/1$，$3/1$，$2/2$，……。

输入格式

输入一个整数 $N$（$1\le N\le 10^7$）。

输出格式

输出表中的第 $N$ 项。

输入输出样例 #1

输入 #1

7

输出 #1

1/4

说明/提示

对于全部测试数据，$1\le N\le 10^7$。

• 2024-11-18 0:30 数据中加入了样例，放在不计分的子任务 2 中。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;// 严格要求 (将long long 类型取别名为ll)
ll a[1010][1010];
int main(){
ios :: sync_with_stdio(0);// 提高cin、cout的运行速度
cin.tie(0);
cout.tie(0);
// 输入重定向
//freopen("in.txt", "r", stdin);
// 输出重定向
//freopen("out.txt", "w", stdout);

ll n;
cin >> n;

a[1][1] = 1;
for(ll j = 2; j <= 1000; j++){
if(j % 2 == 0) a[1][j] = a[1][j – 1] + 1;
else a[1][j] = a[1][j – 1] + j / 2 * 4;
}
for(ll j = 1; j <= 1000; j++){
ll x = 1, y = j, cnt = a[1][j];
if(j % 2 == 0){
while(y >= 1){
x++;
y—;
++cnt;
a[x][y] = cnt;
}
}
else{
while(y >= 1){
x++;
y—;
—cnt;
a[x][y] = cnt;
}
}
}

for(ll i = 1; i <= 1000; i++){
for(ll j = 1; j <= 1000; j++){
//cout << setw(2) << a[i][j] << " ";
if(a[i][j] == n){
cout << i << "/" << j << endl;
return 0;
}
}
}

return 0;
}