坑爹入口

我們想一下，第幾個(gè)生的。那他的孩子就是排在新一波出生的第幾個(gè)上的。

然后我們通過(guò)瞎試得到。10^12<斐波那契的第60項(xiàng)。就是說(shuō)我們不用建圖（也建不下），每次最多60次暴力就可以了。

出題人真是個(gè)人才。

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; long long f[61]; int find(long long val) {int l=1,r=60,mid;while(l<r){mid=(l+r)>>1;if(val>f[mid]) l=mid+1;else r=mid; }return l-1; } long long lca(long long a,long long b) {while(a!=b){if(a<b) swap(a,b);a-=f[find(a)];}return a; } int main() {f[0]=0;f[1]=1;for(int i=2;i<=60;i++) f[i]=f[i-1]+f[i-2];/*printf("%lld",find(11));*/int n;long long a,b;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld%lld",&a,&b);printf("%lld\n",lca(a,b));}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Lance1ot/p/9278785.html

總結(jié)

以上是生活随笔為你收集整理的P3938 斐波那契的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。