题目描述
小C养了一些很可爱的兔子。
有一天,小C突然发现兔子们都是严格按照伟大的数学家 斐波那契 提出的模型来进行繁衍:一对兔子从出生后第二个月起,每个月刚开始的时候都会产下一对小兔子。我们假定,在整个过程中兔子不会出现任何意外。
小C把兔子按出生顺序,把兔子们从1开始标号,并且小C的兔子都是1号兔子和1号兔子的后代。如果某两对兔子是同时出生的,那么小C会将父母标号更小的一对优先标号。如果我们把这种关系用图画下来,前六个月大概就是这样的:
其中,一个箭头A->B表示A是B的祖先,相同的颜色表示同一个月出生的兔子。
为了更细致地了解兔子们是如何繁衍的,小C找来了一些兔子,并且向你提出了m个问题:她想知道关于每两对兔子ai和bi,他们的最近公共祖先是谁。你能帮帮小C吗?
一对兔子的祖先是这对兔子以及他们父母(如果有的话)的祖先,而最近公共祖先是指两对兔子所共有的祖先中,离他们的距离之和最近的一对兔子。比如,5和7的最近公共祖先是2,1和2的最近公共祖先是1,6和6的最近公共祖先是6。
输入
输入第一行,包含一个正整数m。输入接下来m行,每行包含2个正整数,表示ai和bi。
输出
输入一共m行,每行一个正整数,依次表示你对问题的答案。
样例输入
5 1 1 2 3 5 7 7 13 4 12
样例输出
1 1 2 2 4
提示
int n; int a[maxn]; ll fib[maxn]; int main() { fib[1] = 1; for(int i=2;i<=100;i++) fib[i] = fib[i-1] + fib[i-2]; // debug(fib[100]); // debug(fib[80]); n = read; ll x,y; while(n --){ x = read,y = read; while(x ^ y){ if(x > y) swap(x,y); int pos = lower_bound(fib+1,fib+66,y) - fib; pos --; y -= fib[pos]; } printf("%lld\n",x); } return 0; }