10. Bob and a Binary tree

单点时限: 2.0 sec

内存限制: 256 MB

现有一个无限的完全二叉树,每个节点上都标有一个有理数。定义如下:

  • 根节点上的有理数是 1/1

  • p/q 左儿子节点的标记是 p/(p+q)

  • p/q 右儿子节点的标记是 (p+q)/q

如图所示:

按照图示箭头方向,可以遍历得到一个有理数序列:

F(1) = 1/1, F(2) = 1/2, F(3) = 2/1, F(4) = 1/3, F(5) = 3/2, F(6) = 2/3, ...

本题任务是给定 ,计算

输入格式

第一行是一个整数 ,表示测试数据组数。

每组测试数据有一行一个整数

对于约 10% 的数据,有

对于约 30% 的数据,有

输出格式

对于每组测试数据,输出一行形如:Case i: p/q 表示答案。

样例

Input
4
1
4
11
1431655765
Output
Case 1: 1/1
Case 2: 1/3
Case 3: 5/2
Case 4: 2178309/1346269

67 人解决,81 人已尝试。

73 份提交通过,共有 138 份提交。

3.1 EMB 奖励。

创建: 2 年,9 月前.

修改: 2 年,5 月前.

最后提交: 1 月,3 周前.

来源: Greater New York 2016

题目标签
dfs