题解 P3938 【斐波那契】

###解法：斐波拉契### **思路：**很多人直接诶想到了lca吧，但对这道题显然是不可以的。我们考虑列出几项斐波拉契数来查找规律：[1] [2] [3] [4 5] [6 7 8] [9 10 11 12 13]…我们观察一下上述的几项，同一个[]中的是同时出生的，我们发现第i个月出生的兔子恰巧就是它上个月之前的兔子所生，而且对于一个数x，它的直接父亲就是x-f[i](f[i]是第一个比x小的斐波拉契数)，所以我们可以对于每次询问(a,b)，将a、b中较大的数先往前跳到它的父亲，然后比较此时a和b的大小是否相同，若想同则输出该数，若不同则重复上述步骤继续往前跳。说的好像不太清楚，但是我们自己列一列应该很容易看出。举个例子：假设我要询问8和11的最近公共祖先是谁，我们先对11往前跳，即11-8得到了3,此时比较3和8的大小，不相等，so用较大的数8继续往前跳，即8-5=3，此时3和3相等了，所以3就是11和8的最近公共祖先。 **注意：**题目中数据较大到了10的12次方，所以要开long long，此外必须得预处理出斐波拉契中的前60项(因为数据只有10的12次方，斐波拉契的第60项刚好超过了数据范围)，然后就是读入优化(数据有300多万次询问而且数还那么大)，最后在比较时最好二分查找节省时间。 **代码量超少，关键是思路稍微得思考** **代码：** ```cpp #include<bits/stdc++.h> using namespace std; #define ll long long #define il inline ll m,a,b; il ll gi() { int a=0;char x=getchar();bool f=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(); return f?-a:a; } ll c[100]; il void find(ll a,ll b) { if(a<b)swap(a,b); if(a==b){printf("%lld\n",a);return;} int w=lower_bound(c,c+62,a)-c; find(b,a-c[w-1]); } int main() { m=gi(); c[0]=1;c[1]=1; for(int i=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); } return 0; } ```