题目描述
An infinite full binary tree labeled by positive rational numbers is defi ned by:
• The label of the root is 1/1.
• The left child of label p/q is p/(p+q).
• The right child ofl abel p/q is (p+q)/q.
The top of the tree is shown in the following figure:
A rational sequence is defined by doing a level order (breadth first) traversal of the tree (indicated by the light dashed line). So that:
F(1) = 1/1, F(2) = 1/2, F(3) = 2/1, F(4) = 1/3, F(5) = 3/2, F(6) = 2/3, . . .
Write a program which takes as input a rational number, p/q, in lowest terms and fi nds the next rational number in the sequence. That is, if F(n) = p/q, then the result is F(n + 1).
• The label of the root is 1/1.
• The left child of label p/q is p/(p+q).
• The right child ofl abel p/q is (p+q)/q.
The top of the tree is shown in the following figure:
F(1) = 1/1, F(2) = 1/2, F(3) = 2/1, F(4) = 1/3, F(5) = 3/2, F(6) = 2/3, . . .
Write a program which takes as input a rational number, p/q, in lowest terms and fi nds the next rational number in the sequence. That is, if F(n) = p/q, then the result is F(n + 1).
输入
The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set should be processed identically and independently.
Each data set consists of a single line of input. It contains the data set number, K, which is then followed by a space, then the numerator of the fraction, p, followed immediately by a fonward slash (/),followed immediately by the denominator of the fraction, q. Both p and q will be relatively prime and 0 ≤ p, q ≤ 2147483647.
Each data set consists of a single line of input. It contains the data set number, K, which is then followed by a space, then the numerator of the fraction, p, followed immediately by a fonward slash (/),followed immediately by the denominator of the fraction, q. Both p and q will be relatively prime and 0 ≤ p, q ≤ 2147483647.
输出
For each data set there is a single line of output. It contains the data set number, K, followed by a single space which is then followed by the numerator of the fraction, followed immediately by a forward slash (‘/’) followed immediately by the denominator of the fraction. Inputs will be chosen such that neither the numerator nor the denominator will overfl ow a 32-bit integer.
样例输入
5
1 1/1
2 1/3
3 5/2
4 2178309/1346269
5 1/10000000
样例输出
1 1/2
2 3/2
3 2/5
4 1346269/1860498
5 10000000/9999999
【题解】
题意就是让大家根据这颗树构造来跑到下一个点。大家通过观察可以看到，除了最右侧的那个节点外，其他情况都是往上爬树，然后又往下爬。
面对像图 3/2 -> 2/3 这种情况来讲：
1、其实是往上爬，也就是 分子在减少，分母不变。后来发现，一直减去分母直到无法减为止，其实也就是相当于取余运算。
2、然后往右翻一下。分子变成原来的分母，分母变成原来的分母减分子。
3、然后在第一步取余后不是获取了层数吗？然后直接利用层数对分子进行加上分母×层数。
【代码】
异常简单，如果发现规律的话。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int main() 5 { 6 int T,kase; 7 ll p,q; 8 scanf("%d",&T); 9 while(T--){ 10 scanf("%d",&kase); 11 scanf("%lld/%lld",&p,&q); 12 if( q == 1 ){ 13 printf("%d %d/%lld ",kase,1,p+1); 14 }else if( p < q ){ 15 ll tmp = q; 16 q = tmp - p; 17 p = tmp ; 18 printf("%d %lld/%lld ",kase,p,q); 19 }else{ 20 ll dep = 0 ; 21 dep = p/q; 22 23 p = p%q; 24 //printf("Dep : %d ",dep); 25 ll tmp = q; 26 q = tmp - p; 27 p = tmp ; 28 29 //printf("%d %d + %d ",p,q,dep*p); 30 31 q = q + dep*p; 32 printf("%d %lld/%lld ",kase,p,q); 33 } 34 } 35 return 0 ; 36 }