题解 | Cantor表-NOIP1999普及组复赛A题

题目描述

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

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

输入描述:

整数 $N（1≤N≤10000000）$

输出描述:

表中的第N项

示例1

输入

7

输出

1/4

解答

算法1：模拟，按题意一个个枚举

时间复杂度 $O(n)$ ,可以通过本题 $n≤10^7$

算法2：发现Z字形的每条斜线可以快速枚举，即枚举

$\frac{1}{1} ,\frac{1}{2} , \frac{1}{3} , \frac{1}{4} , \frac{1}{5} , \frac{1}{6}……$ 找到要求的第n项所在斜线，再一个个枚举或计算得出答案

时间复杂度 $O(√n)$ ,可以通过 $n≤10^{14}$

算法2.5：枚举第n项在哪一行，计算得出答案，比算法2好写,

时间复杂度同算法2

算法3：发现第i条斜线（即分子分母之和 $=i+1$ 的所有项）中包含 $i\times(i-1)/2+1$ 至 $i\times(i+1)$ 中的每一项，所以可以二分分子分母之和，再根据分子分母之和的奇偶性直接计算第n项

时间复杂度 $O(㏒₂n)$ ,可以通过 $n≤10^{18}$ ,加上高精可通过 $n≤10^{1000}$

二分参考代码：

 #include<iostream>
    #include<cmath>
    using namespace std;
    int main(){
        long long l=1,r,mid,n,a;
        cin>>n;
        r=n;
        while(l<r){
            mid=(l+r)/2;
            if(mid*(mid+1)/2<n)l=mid+1;
            else r=mid;
        }
        a=n-l*(l-1)/2;
        if(l%2==0)cout<<a<<'/'<<l+1-a;
        else cout<<l+1-a<<'/'<<a;
        return 0;
}

来源：cplusplus