[luogu3938][斐波那契]

题目链接

思路

首先可以看出来每个月新增的兔子构成的斐波那契数列。然后每代兔子都可以用斐波那契数列中的一个数来表示。所以对于每只兔子都能在斐波那契数列中找到他所属的一个位置。因为每个兔子都是在两个月之后才开始产下新兔子，所以每个兔子的父亲都是在他所属的斐波那契数前面的前面那一项中。又因为题目中说同一代兔子会按照父亲节点从小到大来从小到大编号。所以可以得出结论，每只兔子的父亲，都可以由这只兔子的编号减去这只兔子所属的斐波那契数列的前一项来得到。然后按照这个结论不断地往上跳就行了。

代码

#include<cstdio>
#include<iostream>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long ll;
ll f[100];
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
ll solve(ll x,ll y) {
    int p = 60;
    while(x != y) {
        if(x < y) swap(x,y);
        while(x <= f[p]) p--;
        x -= f[p];
    }
    return x;
}
int main() {
    f[0] = f[1] = 1;
    for(int i = 2;i <= 61;++i) f[i] = f[i-1] + f[i-2];
    int t = read();
    while(t--) {
        ll x = read(), y = read();
        printf("%lld\n",solve(x,y));
    }
    return 0;
}

一言

这便是险恶的人性,以后面对绝境之时,不要把你的后背交给不信任的人,因为说不定,会有一把意想不到的剑,捅进你的胸口…” ——斗破苍穹