P3938 斐波那契题目背景大样例可在页面底部「附件」中下载。题目描述小 C 养了一些很可爱的兔子。 有一天小 C 突然发现兔子们都是严格按照伟大的数学家斐波那契提出的模型来进行 繁衍一对兔子从出生后第二个月起每个月刚开始的时候都会产下一对小兔子。我们假定 在整个过程中兔子不会出现任何意外。小 C 把兔子按出生顺序把兔子们从 1 开始标号并且小 C 的兔子都是 1 号兔子和 1 号兔子的后代。如果某两对兔子是同时出生的那么小 C 会将父母标号更小的一对优先标 号。如果我们把这种关系用图画下来前六个月大概就是这样的其中一个箭头A→BA \to BA→B表示AAA是BBB的祖先相同的颜色表示同一个月出生的兔子。为了更细致地了解兔子们是如何繁衍的小 C 找来了一些兔子并且向你提出了mmm个问题她想知道关于每两对兔子aia_iai​和bib_ibi​他们的最近公共祖先是谁。你能帮帮小 C 吗一对兔子的祖先是这对兔子以及他们父母如果有的话的祖先而最近公共祖先是指 两对兔子所共有的祖先中离他们的距离之和最近的一对兔子。比如555和777的最近公共祖 先是2,12,12,1和222的最近公共祖先是1,61,61,6和666的最近公共祖先是666。输入格式输入第一行包含一个正整数mmm。输入接下来mmm行每行包含222个正整数表示aia_iai​和bib_ibi​。输出格式输出一共mmm行每行一个正整数依次表示你对问题的答案。输入输出样例 #1输入 #15 1 1 2 3 5 7 7 13 4 12输出 #11 1 2 2 4说明/提示【数据范围与约定】 子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难可以尝试只解决一部分测试数据。 每个测试点的数据规模及特点如下表特殊性质111保证aia_iai​,bib_ibi​均为某一个月出生的兔子中标号最大的一对兔子。例如对 于前六个月标号最大的兔子分别是1,2,3,5,8,131, 2, 3, 5, 8, 131,2,3,5,8,13。特殊性质222保证∣ai−bi∣≤1|a_i-b_i|\le 1∣ai​−bi​∣≤1。C实现#includebits/stdc.husingnamespacestd;#definelllonglong#defineilinlinell m,a,b;il llgi(){inta0;charxgetchar();boolf0;while((x0||x9)x!-)xgetchar();if(x-)xgetchar(),f1;while(x0x9)aa*10x-48,xgetchar();returnf?-a:a;}ll c[100];ilvoidfind(ll a,ll b){if(ab)swap(a,b);if(ab){printf(%lld\n,a);return;}intwlower_bound(c,c62,a)-c;find(b,a-c[w-1]);}intmain(){mgi();c[0]1;c[1]1;for(inti2;i61;i)c[i]c[i-1]c[i-2];//printf(%lld\n,c[i]);while(m--){agi(),bgi();find(a,b);}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容