题目描述
Fibonacci数列的每一项是之前两项的和。 Fibonacci数列以1和2开始，前10项是 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … 输入一个n，求所有小于等于n，且为偶数的Fibonacci数之和。 输入 输入第一行组数T， 接下来T行，每行一个整数n。 (1 <= T <= 23) (1 <= N <= 4000000) 输出 对于每组数据，输出一个数，表示所有小于等于n，且为偶数的Fibonacci数之和。 输入样例 3 10 100 4000000 输出样例 10 44 4613732
代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <climits> #include <cstring> #include <string> #include <algorithm> #include <vector> #include <deque> #include <list> #include <utility> #include <set> #include <map> #include <stack> #include <queue> #include <bitset> #include <iterator> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; const double PI = acos(-1.0); const double E = exp(1.0); const int MOD = 1e9+7; const int MAX = 4000000; int t,n; vector <int> Fib; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); /** 把<=4000000的所有斐波那契数都放入vector */ Fib.push_back(1); Fib.push_back(2); int i = 2; while(Fib[i-2] + Fib[i-1] <= MAX) { Fib.push_back(Fib[i-2] + Fib[i-1]); i++; } cin >> t; while(t--) { cin >> n; /** 找到第一个小于等于n(其实就是lower_bound()函数，只不过vector没有，直接用枚举也可以过)的数的位置, 然后枚举出所有为偶数的斐波那契数求和就可以了。 要注意index要初始化为最后一个位置(因为有可能n比所有的数都要大) */ int index = Fib.size() - 1; for(int i = 0; i < (int)Fib.size(); i++) { if(Fib[i] >= n) { index = i; break; } } if(Fib[index] > n) index--; ll sum = 0; for(int i = 0; i <= index; i++) { if(Fib[i] % 2 == 0) { sum += Fib[i]; } } cout << sum << endl; } return 0; }