单点时限: 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, ...
本题任务是给定 (n),计算 (F(n))。
第一行是一个整数 (T),((1 \leq T \leq 100)),表示测试数据组数。
每组测试数据有一行一个整数 (N),((1 \leq N \leq 2147483647))。
对于约 10% 的数据,有 (1 \leq T \leq 10)。
对于约 30% 的数据,有 (1 \leq N \leq 10^7)。
对于每组测试数据,输出一行形如:Case i: p/q
表示答案。
4 1 4 11 1431655765
Case 1: 1/1 Case 2: 1/3 Case 3: 5/2 Case 4: 2178309/1346269