打卡信奥刷题（2788）用C++实现信奥题 P3938 斐波那契-平芜编程栈

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

输入 #1

5 1 1 2 3 5 7 7 13 4 12

输出 #1

1 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++实现

#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineilinlinell m,a,b;il llgi(){inta=0;charx=getchar();boolf=0;while((x<'0'||x>'9')&&x!='-')x=getchar();if(x=='-')x=getchar(),f=1;while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();returnf?-a:a;}ll c[100];ilvoidfind(ll a,ll b){if(a<b)swap(a,b);if(a==b){printf("%lld\n",a);return;}intw=lower_bound(c,c+62,a)-c;find(b,a-c[w-1]);}intmain(){m=gi();c[0]=1;c[1]=1;for(inti=2;i<=61;i++)c[i]=c[i-1]+c[i-2];//printf("%lld\n",c[i]);while(m--){a=gi(),b=gi();find(a,b);}return0;}