题目描述

现代数学的著名证明之一是 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≤107）。

输出格式

表中的第 N 项。

输入输出样例

输入 #1复制

7

输出 #1复制

1/4

#include<bits/stdc++.h>
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;
    int x = a, y = l + 1 - a;
    if(l % 2 != 0) swap(x, y);
    printf("%d/%d\n", x, y);
    return 0;
}