/ C++党 / 题库 /

[noip1999]Cantor表

[noip1999]Cantor表

时间限制:1s 空间限制:1024KiB


题目来源

本题是1999年普及组的第一题(难度:普及+),希望你能把它做出来,加油!!!^_^

题目描述

小P无意中看到一个现代数学的著名证明是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,…
现在小P想考考你,给你一个整数N,请你告诉他第N项是什么。

输入输出格式

输入格式:

一个整数N。

输出格式:

表中第N项的那个分数。

输入输出样例

Input #1

7

Output #1

1/4

时间和空间限制

每个测试点时间1s,空间1024KiB。

数据范围约定

100%的数据保证1≤N≤100000000。

提供者

Vijos 梁忆炎

信息

难度
4
分类
折半搜索枚举 点击显示
标签
递交数
5
已通过
2
通过率
40%
上传者