Project Euler #2-Even Fibonacci numbers

Tags: Easy

Links: https://www.hackerrank.com/contests/projecteuler/challenges/euler002/problem

---

This problem is a programming version of Problem 2 from projecteuler.net

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed N, find the sum of the even-valued terms.

Input Format

First line contains T that denotes the number of test cases. This is followed by T lines, each containing an integer, N.

Constrains

• $1 \leq T \leq 10^5$
• $10 \leq N \leq 4 \times 10^{16}$

Output Format

Print the required answer for each test case.

Sample Input

2
10
100

Sample Output

10
44

---

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

long FibonacciSum(long limit)
{
    long sum = 0, pre = 1, cur = 2;

    do{
        if (cur % 2 == 0) sum += cur;
        long tmp = pre;
        pre = cur;
        cur = cur + tmp;
    } while(cur <= limit);

    return sum;
}

int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        long n;
        cin >> n;
        long res = FibonacciSum(n);
        cout << res << endl;
    }
    return 0;
}

迭代生成斐波那契数，然后求和即可。优化的思路可以是用一个数组去保存斐波那契数，然后计算前缀和，不过这个前缀和只计算是偶数的前缀和，然后直接$O(1)$得到结果，查找目标值对应第几项斐波那契数，利用二分查找加速。经过测算，斐波那契数达到$4 \times 10^{16}$，也只是第80个数，所以处理起来就很轻松了。

#include <bits/stdc++.h>

using namespace std;

vector<long long> num, preSum;
int len;

void calculate()
{
    preSum.resize(len + 1, 0);
    for (int i = 1; i <= len; ++i) {
        preSum[i] = preSum[i - 1] + ((num[i - 1] & 1) ? 0 : num[i - 1]);
    }
}

void init()
{
    long long target = 4e16;
    num.push_back(1); num.push_back(2);

    long long pre = 1, cur = 2;
    while (true) {
        long long tmp = pre + cur;
        pre = cur;
        cur = tmp;
        if (cur > target) break;
        else num.push_back(cur);
    }
    len = num.size();

    calculate();
}

inline long long solve(long long target)
{
    int pos = upper_bound(num.begin(), num.end(), target) - num.begin();
    return preSum[pos]; 
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    init();

    int caseNum; cin >> caseNum;
    long long target;
    while (caseNum--) {
        cin >> target;
        cout << solve(target) << endl;
    }

    return 0;
}