NG0FRCTN - Fractions on Tree

我们定义一个由分数组成的无限延伸的二叉数有以下规则： 1）每个节点都包含一个分数 2）这个二叉数的根部为1/1 3）任何一个节点i/j都有两个子树：左子树根部的分数为i/(i+j)，右子树的为（i+j)/j 举个例子，深度小于等于3的部分如原图所示：（图没了） 我们把每个节点都表上号且顶端为1，在同一深度的节点的序号从左往右递增。所以序号1为1/1，序号2为1/2，序号3为2/1，等等等等。 你的任务是给你一些数,分别找到序号为这些数的约分后分数。

A fraction tree is an infinite binary tree defined as follows: 1\) Every node of tree contains a fraction 2\) Root of tree contains the fraction 1/1 3\) Any node with fraction i/j has two children : left child with fraction i/(i+j) and right child with fraction (i+j)/j For example , fraction tree upto 3 levels is as shown: ###  We number the nodes according to increasing levels ( root is at level 1) and at any same level , nodes are numbered from left to right. So first node holds the fraction 1/1 , second one holds 1/2 , third one holds 2/1 fourth one holds 1/3 and so on. Your task is simple. Given a number n , you are to find the fraction at the nth node.

Every line of the input contains a single number n. You are to find the fraction at nth node of fraction tree. Input file terminates with a 0 which is not to be processed.

For each input , print numerator and denominator of the lowest form of the fraction seperated by a /. Output of each case to be done in seperate lines.

1
2
3
7
0

1/1
1/2
2/1
3/1