分析：暴力分有90，真良心啊.
a,b这么大，连图都建不出来，肯定是有一个规律.把每个点的父节点写出来：0 1 1 12 123 12345 12345678,可以发现每一个循环的长度刚好是斐波那契数列中的第i项，那么求个前缀和，二分求一下LCA就可以了.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; typedef long long ll; ll sum[], f[], m, a, b; int main()
{
f[] = , f[] = ;
sum[] = , sum[] = ;
for (int i = ; i <= ; i++)
f[i] = f[i - ] + f[i - ], sum[i] = sum[i - ] + f[i];
scanf("%lld", &m);
while (m--)
{
scanf("%lld%lld", &a, &b);
if (a == b)
{
printf("%lld\n", a);
continue;
}
if (a < b)
swap(a, b);
while (a != b && a != && b != )
{
ll l = , r = , res = ;
while (l <= r)
{
ll mid = (l + r) >> ;
if (sum[mid] < a)
{
res = mid;
l = mid + ;
}
else
r = mid - ;
}
a = a - sum[res];
if (b > a)
swap(a, b);
}
if (a == || b == )
printf("1\n");
else
printf("%lld\n", a);
} return ;
}