题解 P3938 【斐波那契】
### 这篇教程会告诉你从零开始思考的历程 ### （可能会是讲的最啰嗦的题解了罢） ### （不过会很易懂） ### 在重点语句处存在下标，体现代码中的语句，便于理解 观察一下不难发现： 用$Rabbit_x$ 表示第 $x$ 天可生兔的兔数量 $Rabbit_1$ = 1 $Rabbit_2$ = 1 对于 $Rabbit_x$ 因为第 $x$ 天，$x - 2$ 天生的兔子可以生了，并且 $x - 1$ 天的兔子自己还能生 所以有 $x$ 天比 $x - 1$ 有多出来的可生的兔子 $ = $ $ x - 2 $ 所以能推导出下面的公式： **$Rabbit_x = Rabbit_{x - 1} + Rabbit_{x - 2}$** .... 这不就是**斐波那契数列**嘛 **所以在程序的开始，我们先打个表$_{(1)}$** ------------ 知道了上面的结论以后，我们可以做进一步推算 在第 $x$ 天总共有 $Rabbit_x$ 只可生的兔子和 $Rabbit_{x - 1}$ 只前一天生的还没有生育能力的兔子 在第 $x$ 天可以生出来 $Rabbit_x$ 只兔子 所以这 $Rabbit_x$ 只兔子如何标号呢？ $Rabbit_x + Rabbit_{x - 1} + 1$ $\rightarrow$ $Rabbit_x + Rabbit_x + Rabbit_{x - 1} + 1$ 对于 $Rabbit_x + Rabbit_{x - 1} + 1$ ~~她~~的母亲的编号是 $1$ 对于 $Rabbit_x + Rabbit_x + Rabbit_{x - 1} + 1$~~她~~的母亲的编号是 $Rabbit_x$ 而$Rabbit_x + Rabbit_{x - 1} = Rabbit_{x + 1}$ $Rabbit_x + Rabbit_x + Rabbit_{x - 1} = Rabbit_{x + 2}$ 而对于其中编号为 ${x} (x ∈ (Rabbit_{x + 1} + 1, Rabbit_{x + 2} + 1))$的兔子 , 可以求得~~她~~的母亲的编号是： $x - Rabbit_{x + 1}$ ... 又一个奇怪的结论增加了 ------------ 知道了上面的结论以后，我们又可以做进一步推算 对于两个兔子 $a,b$ **编号大的辈数一定不小于编号小的$_{(3)}$** 我们需要先找到~~她~~俩所在的编号范围 **所以我们可以从编号大的求他的母亲$_{(4)}$** 然后如此反复 反复下去，反复下去 **总有一天，终将会找到他的祖先$_{(2)}$** ~~（泪目）~~ --- ### _AC Code_ ```cpp #include <cstdio> #include <algorithm> using namespace std; long long m, a, b; long long fibor[] = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920}; //(1) 打一个斐波那契数列表 作用上文已阐述 int main() { scanf("%lld", &m); // 读入数据组数 while (m--) { scanf("%lld%lld", &a, &b); // 读入a,b while (a != b) // (2) 如果 a 与 b 相同，说明已经找到了他们的祖先 { if (a > b) // (3) 比较编号大小 a -= (*(lower_bound(fibor, fibor + 58, a) - 1)); // (4) 找妈妈 直接用妈妈的编号覆盖崽的编号 else b -= (*(lower_bound(fibor, fibor + 58, b) - 1)); // (4) 找妈妈 直接用妈妈的编号覆盖崽的编号 } printf("%lld\n",a); // 祖先找到了 输出祖先 } return 0; } ```
<<< Return to archive list