思路
脑子还真的是好东西，自己太笨了
容易发现父亲节点和儿子节点的关系
儿子节点大于父亲节点
儿子节点和父亲节点之差为斐波那契数，且斐波那契数为小于儿子节点的最大的一个
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;
}