P3938 斐波那契

思路

脑子还真的是好东西，自己太笨了
容易发现父亲节点和儿子节点的关系
儿子节点大于父亲节点
儿子节点和父亲节点之差为斐波那契数，且斐波那契数为小于儿子节点的最大的一个
1e12中有60左右的斐波那契数，打出表来查找就好了，深度不超过60

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn = 70;
inline ll read() {
    ll x = 0, f = 1; char s = getchar();
    for (; s < '0' || s > '9'; s = getchar()) if (s == '-') f = -1;
    for (; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';
    return x * f;
}
int n;
ll f[maxn]={1,1};
ll a[maxn];
map<ll,int> dsr;
ll lca(ll x,ll y) {
    dsr.clear();
    dsr[x]=1;
    while(x) {
        x=x-f[lower_bound(f+1,f+1+59,x)-f-1];
        dsr[x]=1;
    }
    if(dsr[y]) return y;
    while(y) {
        y=y-f[lower_bound(f+1,f+1+59,y)-f-1];
        if(dsr[y]) return y;
    }
    return 1;
}
int main() {
    FOR(i,2,59) f[i]=f[i-1]+f[i-2];
    n=read();
    FOR(i,1,n) {
        ll x=read(),y=read();
        printf("%lld\n",lca(x,y));  
    }
    return 0;
}