【题解】
我们可以发现，对于一只编号为a的兔子，a的父亲的编号是a-f[x]，其中x为a出生的月份。
而计算a出生月份的方法是：找到第一个大于等于a的f[x],x即为a出生的月份。
那么我们只要不断的找a与b的父亲，直到它们相等即可。
1 #include<cstdio> 2 #include<algorithm> 3 #define LL long long 4 using namespace std; 5 const int maxn=300010; 6 LL n,m,a,b; 7 LL f[maxn]; 8 void read(LL &k){ 9 k=0; int f=1; char c=getchar(); 10 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 11 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 12 k*=f; 13 } 14 inline LL find(LL a,LL &last){ 15 int l=1,r=last,mid; 16 while(l<r)if (f[mid=(l+r)>>1]>=a) r=mid; else l=mid+1; 17 last=l-1; return a-f[l-1]; 18 } 19 int main(){ 20 f[0]=1; f[1]=1; 21 for (int i=2;i<=60;i++)f[i]=f[i-1]+f[i-2]; 22 read(m); 23 for (int i=1;i<=m;i++){ 24 read(a); read(b); 25 LL posa=60,posb=60; 26 while(a!=b&&a>1&&b>1){ 27 if (a>b) a=find(a,posa); 28 else b=find(b,posb); 29 } 30 printf("%lld ",a==b?a:1); 31 } 32 return 0; 33 }