洛谷——P1014 Cantor表

时间:2023-03-09 06:05:37
洛谷——P1014 Cantor表

P1014 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项

输入输出样例

输入样例#1: 复制
7
输出样例#1: 复制
1/4

数学

找规律

我们来看一下这个题的一个小规律

1/1

1/2  2/1

3/1  2/2  1/3

1/4  2/3  3/2  4/1

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

1/6  2/5  3/4  4/3  5/2  6/1

、、、、、、、、、、、、、、、、、、、

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 10000010
using namespace std;
int n,s,q,s1,s2;
int read()
{
    ,f=; char ch=getchar();
    ;ch=getchar();}
    +ch-',ch=getchar();
    return x*f;
}
int main()
{
    n=read();
    ;i;i++)
     if((s+=i)>=n)
     {
         s-=i;
         q=i; break;
     }
    ==)
    {
        s1=n-s;
        s2=q-(n-s-);
    }
    else
    {
        s2=n-s;
        s1=q-(n-s-);
    }
    printf("%d/%d",s1,s2);
    ;
}