【NOIP1999】cantor表

题目描述

现代数学的著名证明之一是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（1≤N≤10000000）

输出格式

输出：表中的第N项

样例数据

input

7

output

1/4

数据规模与约定

时间限制：1s

空间限制：256MB

#include <iostream>
using namespace std;
int main()
{
	freopen("cantor.in","r",stdin);
    freopen("cantor.out","w",stdout);
  int s=0;
  int delt=0;
  int N;
  cin>>N;
  while(s<N){
    delt++;
    s+=delt;
  }
  int i=s-N;
  if(delt%2==0){
    cout<<delt-i<<"/"<<1+i;
  }
  else
  {
    cout<<1+i<<"/"<<delt-i;
  }
  return 0;
}