【思维】P1014 Cantor表

https://www.luogu.com.cn/problem/P1014

题目描述

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

…

我们以 Z 字形给上表的每一项编号。第一项是

输入格式

整数 $10^71≤N≤107）。$

输出格式

表中的第

输入输出样例

输入 #1

输出 #1

1/4

思路：

将前4条斜线上的元素按项序排列后，再以元素所在斜线的行数为单位划分，观察后可总结出规律。
1/1，  1/2 2/1，  3/1 2/2 1/3， 1/4，2/3，3/2，4/1
第1条   第2条       第3条        第4条

通过观察可发现，第偶数条中元素，分子正序，分母逆序；第奇数条中元素，分子逆序，分母正序。

代码：

#include<bits/stdc++.h>
using namespace std;
long n,i,j;  //i为斜线条数，j为前i条斜线元素总数 
int main(){     
    cin>>n;    
    while(j<n){    //找到第n项在第几条斜线上 
        i++;
        j += i;
    } 
    if(i%2==0) cout<<i-(j-n)<<'/'<<(j-n)+1; //i为偶数时，分子正序，分母逆序 
    else cout<<(j-n)+1<<'/'<<i-(j-n);    //i为奇数时， 分子逆序，分母正序 
    return 0;
}

为什么写成博客？

发现了规律，然而没有打通解题思路。看了题解 P1014 【Cantor表】后才得到找出第n项在第i条的思路。