SNNU1338: ACMer日常训练，第5弹——袁学长第一弹??
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 17 Solved: 3 [Submit][Status][Web Board]Description
定义一种二叉树，根节点是（1，1）,二叉树构造方法：
设根节点是(a,b)，则它的左儿子是(a+b,b),右儿子是(a,a+b)；例如上面的根节点的左右儿子分别是(2,1),(1,2)。
现在给你一个(i,j)，问从(1,1)这个根节点走到(i,j)节点向左走多少次，向右走多少次？
Input
第一行测试个数T；(1<=T<=7)
下来每行表示一组测试数据，包含i,j两个整数。
(1<= i,j <=2e9)
Output
每组输出l r，l表示向左走多少步，r表示向右走多少步。
Sample Input
3
42 1
3 4
17 73
Sample Output
41 0
2 1
4 6
Source
SNNUOJ1338（该OJ只有SNNU内网可登）
——————————
这道题考察的很巧妙，第一眼以为是要构造二叉树或者DFS，但是对于2E9的测试数据这两个显然不成立。
于是想通过模拟来进行，但是如果从上往下进行模拟，样例1和2很好过，但是3我发现并不好过。
于是想到显然可以从下往上进行，但是如果是a-b一步步模拟的话，会T。
于是考虑用除法加速减法的过程，但是要注意除法和mod会有0的问题，在这里没处理好WA了几发，多亏袁学长帮助……处理了一下0的问题。
——————
代码如下：
#include<iostream>
using namespace std;
namespace miao
{
intleft , right ;
}
void gcd( int a , int b )
{
if(a == 0 && b == 0 )
return;
if(a > b )
{
if(a % b == 0 )
{
miao::left+=a/b - 1 ;
gcd(1,b);
}
else
{
miao::left+=a/b;
gcd(a%b,b);
}
}
if(a < b )
{
if(b % a == 0 )
{
miao::right+=b/a-1;
gcd(a,1);
}
else
{
miao::right+=b/a;
gcd(a,b%a);
}
}
}
int main()
{
intt ;
cin>> t ;
while(t--)
{
inti , j ;
cin>> i >> j ;
miao::left=0,miao::right=0;
gcd(i,j);
cout<< miao::left <<‘ ‘<< miao::right << endl ;
}
}
原文：http://www.cnblogs.com/xiekeyi98/p/6280300.html