题目链接：https://www.cnblogs.com/Juve/articles/11295333.html
A：
考场上只有70分。。。
发现几个性质：特殊性质1：在两条链上，看它是fib第几项，同为奇数项或偶数项就输出小的，否则输出1
特殊性质2：a==b，输出a，否则输出1
你就70啦：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cmath>
#define MAXN 300005
#define int long long
#define re register
using namespace std;
int m,anc[16][16]={{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,1,2,1,1,2,1,2,1,1,2,1,1,2,1,2},{0,1,1,3,1,1,1,1,3,1,1,3,1,1,1,1},{0,1,1,1,4,1,1,1,1,1,1,1,4,1,1,1},{0,1,2,1,1,5,1,2,1,1,2,1,1,5,1,2},{0,1,1,1,1,1,6,1,1,1,1,1,1,1,1,1},{0,1,2,1,1,2,1,7,1,1,2,1,1,2,1,2},{0,1,1,3,1,1,1,1,8,1,1,3,1,1,1,1},{0,1,1,1,1,1,1,1,1,9,1,1,1,1,1,1},{0,1,2,1,1,2,1,2,1,1,10,1,1,2,1,2},{0,1,1,3,1,1,1,1,3,1,1,11,1,1,1,1},{0,1,1,1,4,1,1,1,1,1,1,1,12,1,1,1},{0,1,2,1,1,5,1,2,1,1,2,1,1,13,1,2},{0,1,1,1,1,1,1,1,1,1,1,1,1,1,14,1},{0,1,2,1,1,2,1,2,1,1,2,1,1,2,1}};
int fib[65];
signed main(){
scanf("%lld",&m);
if(m<=12){
for(re int i=1,a,b;i<=m;i++){
scanf("%lld%lld",&a,&b);
printf("%lld\n",anc[a][b]);
}
return 0;
}
fib[0]=fib[1]=1;
for(re int i=2;i<=60;i++){
fib[i]=fib[i-1]+fib[i-2];
//cout<<fib[i]<<endl;
//if(fib[i]>1e12){
// cout<<i<<endl;
// break;
//}
}
for(re int i=1,a,b;i<=m;i++){
scanf("%lld%lld",&a,&b);
if(a==b) printf("%lld\n",a);
else if(abs(a-b)==1) puts("1");
else{
re int aa=0,bb=0;
for(re int j=1;j<=60;j++){
if(fib[j]==a){
aa=j;
}
if(fib[j]==b){
bb=j;
}
if(aa*bb!=0) break;
}
if((aa&1)==(bb&1)){
printf("%lld\n",fib[min(aa,bb)]);
}else puts("1");
}
}
return 0;
}
然而。。。
打正解：
100 分做法： 我们来研究一下这个神秘的力量： 依次写下兔子们的标号和他们父亲（从 2 开始）： 1 1 1 2 1 2 3 1 2 3 4 5 … 发现其实一定是许多连续段的从 1 开始的序列组合到一起，每段长度依次是斐波那契数列里面的每一项。
于是我们发现，对于$fib(i)<=x<=fib(i+1),father(x)=x-fib(i)$
所以我们可以像lca一样，一个一个向上跳
因为$fib(60)>1e12$，所以复杂度可以接受
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #include<cmath> #define ll long long #define re register using namespace std; ll m,fib[65]; void get_lca(ll a,ll b){ if(a<b) swap(a,b); if(a==b){ printf("%lld\n",a); return ; } ll aa=lower_bound(fib+1,fib+60+1,a)-fib; get_lca(b,a-fib[aa-1]); } signed main(){ scanf("%lld",&m); fib[0]=fib[1]=1; for(re int i=2;i<=61;i++) fib[i]=fib[i-1]+fib[i-2]; for(ll i=1,a,b;i<=m;i++){ scanf("%lld%lld",&a,&b); get_lca(a,b); } return 0; }
C:
留坑
原文：https://www.cnblogs.com/Juve/p/11295460.html