P1014 Cantor表

本文轉載於洛谷https://www.luogu.com.cn/blog/home/solution-p1014

#include<stdio.h>
#include<math.h>

    int main(){
        long long l=1, r, mid, n, a;
        scanf("%d", &n);
        r=n;				//r是臨時變數 
        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)
            printf("%d/%d", a, l+1-a);
        else 
            printf("%d/%d", l+1-a, a);
        return 0;
}

演算法3：發現第i條斜線（即分子分母之和=i+1的所有項）中包含i*(i-1)/2+1至i*(i+1)中的每一項，所以可以二分分子分母之和，再根據分子分母之和的奇偶性直接計算第n項

時間複雜度O(㏒₂n),可以通過n≤10^{18,加上高精可通過n≤10}1000