1450: Bird tree
题目描述
The Bird tree is an infinite binary tree, whose first 5 levels look as follows:
It can be defined as follows:
This is a co-recursive definition in which both occurrences of bird refer to the full (infinite) tree. The expression bird + 1 means that 1 is added to every fraction in the tree, and 1∕bird means that every fraction in
the tree is inverted (so a∕b becomes b∕a).
Surprisingly, the tree contains every positive rational number exactly once, so every reduced fraction is at a unique place in the tree. Hence, we can also describe a rational number by giving directions (L for left subtree, R for right subtree) in the Bird
tree. For example, 2∕5 is represented by LRR. Given a reduced fraction, return a string consisting of L’s and R’s: the directions to locate this fraction from the top of the tree.
输入
On the first line a positive integer: the number of test cases, at most 100. After that per test case:
- one line with two integers a and b (1 ≤ a,b ≤ 109), separated by a ’/’. These represent the numerator and denominator of a reduced fraction. The integers a and b are not both equal to 1, and they satisfy
gcd(a,b) = 1.
For every test case the length of the string with directions will be at most 10 000.
输出
Per test case:
- one line with the string representation of the location of this fraction in the Bird tree.
样例输入
样例输出
报告人：SpringWater（GHQ）
leftchild[1……2^N] = a/(a + b);
rightchild[1……2^N] = (a + b) /b;
#include<stdio.h>
int main()
{
int a,b,cas,t;
scanf("%d",&cas);
while(cas--)
{
scanf("%d/%d",&a,&b);
while(!(a==1&&b==1))
if(a>b)putchar('R'),t=a,a=b,b=t-b;
else putchar('L'),t=a,a=b-a,b=t;
putchar('\n');
}
return 0;
}