洛谷3938 斐波那契

题意

略（太复杂了不想写）

题解

令 $f[i]$ 为不大于 $x$ 的最大斐波那契数，那么 $x$ 的父亲节点就是 $x-f[i]$ 。

斐波那契数列的第 $58$ 项刚好小于 $10^{12}$ ，所以预处理前 $58$ 个就行了。求两个节点的 $\text{LCA}$ 可以用一种类似树剖的方法，不断地取 $u$ 和 $v$ 中的较大值跳到父节点，直到 $u$ 和 $v$ 相等。

层数最多只有 $58$ 层，复杂度 $O(m)$。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

ll n,a,b,f[65];

inline void init() //预处理
{
    f[0]=f[1]=1;
    for (ll i=2;i<=58;i++) f[i]=f[i-1]+f[i-2];
}

inline ll qRange(ll u,ll v)
{
    while (u!=v)
    {
        if (u<v) swap(u,v);
        ll pos=lower_bound(f+1,f+59,u)-f-1; //找到小于 u 的数
        u-=f[pos];
    }
    return u;
}

signed main()
{
    init();
    n=read();
    while (n--)
    {
        a=read(); b=read();
        printf("%lld\n",qRange(a,b));
    }
    return 0;
}