[Project Euler #2]Fibonacci Numbers 题解

一道很有意思的推式子题。

不难发现$Fibonacci$数列是

$$odd,odd,even,odd,odd,even...$$

也就是说$F(3),F(6),F(9)…$都是偶数。那么我们只需要摸索出一个$F(n)$与$F(n - 3)$和$F(n - 6)$的关系即可。

首先我们先通过一步简单的推导推出一个东西：

$$\begin{aligned} F(n)&=F(n-1)+F(n-2)\\ &=F(n-2)+F(n-3)+F(n-2)\\ &=2F(n - 2) + F(n - 3)\\ \end{aligned}$$

然后我们来继续硬拆：

$$\begin{aligned} F(n)&=2F(n - 2) + F(n - 3)\\ &=2(F(n - 3) + F(n - 4)) + F(n - 3)\\ &=3F(n - 3) + 2F(n - 4)\\ &=3F(n - 3) + 2(F(n - 5) + F(n - 6))\\ &=3F(n - 3) + 2F(n - 5) + 2F(n - 6)\\ \end{aligned}$$

然后我们发现，因为一开始我们推出来了个部分结论，于是

$$F(n - 3) = 2F(n - 5) + F(n - 6)$$

变形之后得到

$$2F(n - 5) = F(n - 3) - F(n - 6)$$

代入第二部分计算：

$$\begin{aligned} F(n)&=3F(n - 3) + 2F(n - 5) + 2F(n - 6)\\ &=3F(n - 3) + F(n - 3) - F(n - 6) + 2F(n - 6)\\ &=4F(n - 3) + F(n - 6)\\ \end{aligned}$$

于是就愉快的做完了。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include <bits/stdc++.h> #define dbg(x) std::cerr << #x << " = " << x << "\n" using namespace std; typedef long long ll; ll t, n; int main() { scanf("%lld", &t); while(t--) { scanf("%lld", &n); ll a = 2, b = 8, nowsum = 10; while(1) { if(4 * b + a > n) { cout << nowsum << endl; break; } nowsum += 4 * b + a; ll cp = b; b = 4 * b + a; a = cp; } } return 0; }