## 引用

### 题目描述

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 105$
$10 \leq$ N $\leq 4 \times 10 {16}$

2
10
100

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.

### 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;
}

Q.E.D.