更好的阅读体验

引用

虽然知道这是一道数论题，但优先想到的还是怎么递推或者递归求解。看到评论区大佬的题解后发现还能这么玩？？？

关于为什么可以这么玩，可以看看第二个大佬的题解

Mehul Singh Rathore 找到大佬的评论就能看到

自来也sama 欧垃计划Level-1解题总结

题目描述

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.

Output Format

Print the required answer for each test case.

Constraints

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

Sample Input 0

2
10
100

Sample Output 0

10
44

Explanation 0

For N =10, we have {2,8}, sum is 10.
For N =100, we have {2,8,34}, sum is 44.

算法

(数论) $O(1)$

从数据范围上看可能会TLE，但实际上计算斐波那契数列值最接近 $4 \times 10^{16}$并不需要多久，所以对于这个我们可以直接暴力去算。
但好歹他也是个数论题，你这样暴力就有点说不过去了，既然涉及数学知识那么就应该用数学知识来解决。

从题目我们可以发现每三个数就会出现一次偶数。而斐波那契数列又具有f(n) = f(n - 1) + f(n - 2)的性质，那么我们可以往这方面想，因为一个序列如果满足一种性质，那么满足一定规律的子序列同样也会满足相似的性质。比如等差数列，我们从第一个开始，每三个取一个数，构成的新数列同样也满足等差数列的性质。

我们仔细看看 0 2 8这三个数，发现第三个数是前一个数的四倍加上前二个数，即E(n) = 4 $\times$ E(n - 1) + E(n - 2)。那么我们只需要计算一下这样的新斐波那契数列中小于N的前n项的和就行了

时间复杂度 $O(1)$

直接套公式

C++ 代码

#include <iostream>

using namespace std;

typedef long long LL;

int n;

int main()
{
    cin >> n;

    // 常规递推    
    // while (n --)
    // {
    //     LL t , res = 0 , a = 1 , b = 1 , c;

    //     cin >> t;

    //     for(int i = 1; ; i ++)
    //     {
    //         c = a + b;
    //         a = b;
    //         b = c;
    //         if(c < t && !(c & 1)) res += c;
    //         if(c > t) break;

    //     }
    //     cout << res << endl;
    // }

    // 构建新的斐波那契数列
    while (n --)
    {
        LL t , res = 2 , a = 0 , b = 2 , c;

        cin >> t;

        for(int i = 1; ; i ++)
        {
            c = a + 4 * b;
            a = b;
            b = c;
            if(c < t) res += c;
            if(c > t) break;

        }
        cout << res << endl;
    }

    return 0;
}