第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海）G Fibonacci

题目

In mathematics, the Fibonacci numbers, commonly denoted as f_nf
n
​
, is a sequence such that each number is the sum of the two preceding numbers, starting with ({1}) and ({1}). That is, (f_1=1,f_2 =1) and (f_n = f_{n-2} + f_{n-1}~(n ge 3))Thus, the beginning of the sequence is (1, 1, 2, 3, 5, 8, 13, 21,ldots1,1,2,3,5,8,13,21,… .)

题意

给出一个函数(g(f_i,f_j)) 定义为斐波那契数列的第i项和第j项相乘为偶数函数值为1 否则函数值为0，给定一个n,求i从1到n，j从i+1到n所有的(g(f_i,f_j))累加和

思路

根据斐波那契 奇奇偶 奇奇偶 ... 的规律 先算出来偶数的数量(even = n/3) 统计时推出公式为(ans = (even * even - even) / 2 + (n - even) * even;) 别忘记开long long即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n;
    scanf("%lld", &n);
    ll even = n/3; // 偶数的个数 
    ll ans = (even * even - even) / 2 + (n - even) * even; // 推出的公式 
    cout << ans << "
";
}

/*
1 1 2 3 5 8 13 21 34
1 1 2 1 1 2 1 1 2 
*/