九度Online Judge

本次比赛采取按照case给分的模式,请大家提交时,通过点击“详情”查看!
程序输入输出请尽量使用scanf和printf!
第四题,走到.之后会有几率往回走。

 题目1-九度Online Judge,用代码记录你的成长之路!

题目1:无限完全二叉树的层次遍历

时间限制:1 秒

内存限制:128 兆

特殊判题:

提交:1031

解决:192

题目描述:

有一棵无限完全二叉树,他的根节点是1/1,且任意一个节点p/q的左儿子节点和右儿子节点分别是,p/(p+q)和(p+q)/q。如下图:

它的层次遍历结果如下:
1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1,...
有如下两类问题:
1.找到层次遍历的第n个数字。如,n为2时,该数字为1/2;
2.给定一个数字p/q,输出它在层次遍历中的顺序,如p/q为1/2时,其顺序为2;

输入:

输入包含多组测试用例,输入的第一行为一个整数T,代表共有的测试用例数。
接下去T行每行代表一个测试用例,每个测试用例有如下两种类型
1.1 n。输出层次遍历中,第n个数字。
2.2 p q。输出p/q在层次遍历中的顺序。
1 ≤ n, p, q ≤ 2^64-1

输出:

对于每个测试用例,若其类型为1,输出两个整数p q,代表层次遍历中第n个数字为p/q。
若其类型为2,输出一个整数n,代表整数p/q在层次遍历的中的顺序n。
数据保证输出在[1,2^64-1]范围内。

样例输入:
4
1 2
2 1 2
1 5
2 3 2
样例输出:
1 2
2
3 2
5