In the late XIXth century the German mathematician George Cantor argued that the set of positive fractions Q+ is equipotent to the set of positive integers N, meaning that they are both infinite, but of the same class. To justify this, he exhibited a mapping from N to Q+ that is onto. This mapping is just traversal of the N × N plane that covers all the pairs:The first fractions in the Cantor mapping are:
Write a program that finds the i-th Cantor fraction followingthe mapping outlined above.
Input
The inputs consists of several lines with a positive integer number i each one.
Output
The output consists of a line per input case, that contains the i-th fraction, with numerator and denominator separed by a slash ‘/’. The fraction should not be in the most simple form.
Sample Input
6
Sample Output
1/3
问题链接：UVA880 Cantor Fractions
问题简述：（略）
问题分析：
这个问题的关键是找出计算下标的规律。
第k个三角形包含前k(k+1)/2个元素，每次从左上角向下移动，横纵坐标之和为k+1。计算比n小并且满足k(k+1)/2的k值，然后利用n-k(k+1)/2计算出位置。
程序说明：（略）题记：（略）
参考链接：（略）
AC的C++语言程序如下：
/* UVA880 Cantor Fractions */ #include <iostream> #include <climits> using namespace std; long long bs(long long key) { long long left = 0, right = INT_MAX, mid; while(left < right) { mid = (left + right + 1) / 2; if (mid * (mid + 1) / 2 >= key) right = mid - 1; else left = mid; } return left; } int main() { long long n, b, m; while(cin >> n) { m = bs(n); b = n - m * (m + 1) / 2; cout << m + 2 - b << "/" << b << endl; } return 0; }