Rockdu's Blog

题目背景

大样例下发链接：http://pan.baidu.com/s/1c0LbQ2 密码：jigg

题目描述

小 C 养了一些很可爱的兔子。 有一天，小 C 突然发现兔子们都是严格按照伟大的数学家斐波那契提出的模型来进行 繁衍：一对兔子从出生后第二个月起，每个月刚开始的时候都会产下一对小兔子。我们假定， 在整个过程中兔子不会出现任何意外。

小 C 把兔子按出生顺序，把兔子们从 1 开始标号，并且小 C 的兔子都是 1 号兔子和 1 号兔子的后代。如果某两对兔子是同时出生的，那么小 C 会将父母标号更小的一对优先标 号。

如果我们把这种关系用图画下来，前六个月大概就是这样的：

其中，一个箭头 A → B 表示 A 是 B 的祖先，相同的颜色表示同一个月出生的兔子。

为了更细致地了解兔子们是如何繁衍的，小 C 找来了一些兔子，并且向你提出了 m 个 问题：她想知道关于每两对兔子 a_iai​和 b_ibi​ ，他们的最近公共祖先是谁。你能帮帮小 C 吗？

一对兔子的祖先是这对兔子以及他们父母（如果有的话）的祖先，而最近公共祖先是指 两对兔子所共有的祖先中，离他们的距离之和最近的一对兔子。比如，5 和 7 的最近公共祖 先是 2，1 和 2 的最近公共祖先是 1，6 和 6 的最近公共祖先是 6。

输入输出格式

从标准输入读入数据。 输入第一行，包含一个正整数 m。 输入接下来 m 行，每行包含 2 个正整数，表示 a_iai​ 和 b_ibi​ 。

输出到标准输出中。 输入一共 m 行，每行一个正整数，依次表示你对问题的答案。

输入输出样例

5 
1 1 
2 3 
5 7 
7 13 
4 12

1 
1 
2 
2 
4

说明

【数据范围与约定】 子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解 决一部分测试数据。 每个测试点的数据规模及特点如下表：

特殊性质 1：保证 a_iai​, b_ibi​ 均为某一个月出生的兔子中标号最大的一对兔子。例如，对 于前六个月，标号最大的兔子分别是 1, 2, 3, 5, 8, 13。

特殊性质 2：保证 |a_i-b_i|\le 1∣ai​−bi​∣≤1。

fstqwq大佬出的题果然6。看了半天终于发现一个数减去严格比它小的最大的斐波那契数就是他的父亲节点编号。而即使在1e12下这棵树的高度也只有56（56个斐波那契数），所以我们记录路径进行比较就行了。

#include<cstdio>
#include<cctype>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 105;
LL fib[105], l, r;
LL path[205], len;
int m, cnt;

inline char gc() {
    static char buf[10000000], *p1 = buf, *p2 = buf;
    return ((p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)) ? EOF : *p1++;
}

template<typename T>
inline void read(T & x) {
    x = 0;static char c = gc();
    while(!isdigit(c)) c = gc();
    while(isdigit(c)) x = (x << 1) + (x << 3) + c - '0', c = gc();
}

int DF(int L, int R, LL num) {
    while(L	< R - 1) {
        int mid = L + R >> 1;
        if(fib[mid] < num) L = mid;
        else R = mid;
    }
    return L;
}

LL query(LL x, LL y) {
    int dx = DF(1, cnt + 1, x);
    int dy = DF(1, cnt + 1, y);
    len = 0;
    while(x != 1) 
        path[++len] = x, x -= fib[dx], dx = DF(1, dx, x);
    while(y != 1) 
        path[++len] = y, y -= fib[dy], dy = DF(1, dy, y);
    sort(path + 1, path + 1 + len);
    for(register int i = len; i >= 2; --i)
        if(path[i] == path[i - 1])
           return path[i];
    return 1;
}

int main() {
    read(m);
    fib[1] = 1, fib[2] = 2, cnt = 2;
    while(fib[cnt] + fib[cnt - 1] <= 1e12)
        fib[++cnt] = fib[cnt - 1] + fib[cnt - 2];
    while(m--) {
        read(l), read(r);
        if(l == r) {
            printf("%lld\n", l);
            continue;
        }
        printf("%lld\n", query(l, r));
    }
    return 0;
}