时间限制: 1.000 Sec 内存限制: 128 MB题目描述小C养了一些很可爱的兔子。有一天小C突然发现兔子们都是严格按照伟大的数学家斐波那契提出的模型来进行繁衍一对兔子从出生后第二个月起每个月刚开始的时候都会产下一对小兔子。我们假定在整个过程中兔子不会出现任何意外。小C把兔子按出生顺序把兔子们从1开始标号并且小C的兔子都是1号兔子和1号兔子的后代。如果某两对兔子是同时出生的那么小C会将父母标号更小的一对优先标号。如果我们把这种关系用图画下来前六个月大概就是这样的其中一个箭头A-B表示A是B的祖先相同的颜色表示同一个月出生的兔子。为了更细致地了解兔子们是如何繁衍的小C找来了一些兔子并且向你提出了m个问题她想知道关于每两对兔子和他们的最近公共祖先是谁。你能帮帮小C吗一对兔子的祖先是这对兔子以及他们父母如果有的话的祖先而最近公共祖先是指两对兔子所共有的祖先中离他们的距离之和最近的一对兔子。比如5和7的最近公共祖先是21和2的最近公共祖先是16和6的最近公共祖先是6。输入输入第一行包含一个正整数m。输入接下来m行每行包含2个正整数表示和。输出输入一共m行每行一个正整数依次表示你对问题的答案。样例输入5 1 1 2 3 5 7 7 13 4 12样例输出1 1 2 2 4提示解题思路Fibonacci数列F(1)1F(2)1F(3)2F(4)3F(5)5F(6)8F(7)13F(8)21………………将所有的Fibonacci数放入数组bit中。可以发现规律11的祖先是其本身2在bit中小于2的最大的数是12的祖先是2-113在bit中小于3的最大的数是23的祖先是3-214在bit中小于4的最大的数是34的祖先是4-315在bit中小于5的最大的数是35的祖先是5-326在bit中小于6的最大的数是56的祖先是6-517在bit中小于7的最大的数是57的祖先是7-528在bit中小于8的最大的数是58的祖先是8-539在bit中小于9的最大的数是89的祖先是9-8110在bit中小于10的最大的数是810的祖先是10-8211在bit中小于11的最大的数是811的祖先是11-8312在bit中小于12的最大的数是812的祖先是12-8413在bit中小于13的最大的数是813的祖先是13-85…………………………………………………………在本题中规定1的辈份最大那么标号越大辈份越小所以求两个数a和b的LCA如果aba就是LCA(ab)。如果a!b如果ab更新a为a的祖先否则更新b为b的祖先。重复该操作直到ab。Accepted Code#includebits/stdc.h #define ll long long using namespace std; const ll limit1e1210; vectorllbit; void initialize(){ bit.push_back(1); bit.push_back(1); ll a1,b1; while(alimit){ ll tmpa; aab; btmp; bit.push_back(a); } } ll get_father(ll x){ if(x1)return 1; auto itlower_bound(bit.begin(),bit.end(),x); if(itbit.end())return x-bit.back(); else{ it--; return x-*it; } } ll lca(ll a,ll b){ while(a!b){ if(ab)aget_father(a); else bget_father(b); } return a; } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); initialize(); ll m; cinm; while(m--){ ll a,b; cinab; coutlca(a,b)\n; } return 0; }