第 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
{1}
1 and
1
{1}
1. That is,
f
1
=
1
,
f
2
=
1
f_1=1,f_2 =1
f1=1,f2=1 and
f
n
=
f
n
−
2
+
f
n
−
1
(
n
≥
3
)
f_n = f_{n-2} + f_{n-1}~(n \ge 3)
fn=fn−2+fn−1 (n≥3)Thus, the beginning of the sequence is
1
,
1
,
2
,
3
,
5
,
8
,
13
,
21
,
…
1
,
1
,
2
,
3
,
5
,
8
,
13
,
21
,
…
.
1, 1, 2, 3, 5, 8, 13, 21,\ldots1,1,2,3,5,8,13,21,… .
1,1,2,3,5,8,13,21,…1,1,2,3,5,8,13,21,….
题意
给出一个函数 g ( f i , f j ) g(f_i,f_j) g(fi,fj) 定义为斐波那契数列的第i项和第j项相乘为偶数函数值为1 否则函数值为0,给定一个n,求i从1到n,j从i+1到n所有的 g ( f i , f j ) g(f_i,f_j) g(fi,fj)累加和
思路
根据斐波那契 奇奇偶 奇奇偶 … 的规律 先算出来偶数的数量 e v e n = n / 3 even = n/3 even=n/3 统计时推出公式为 a n s = ( e v e n ∗ e v e n − e v e n ) / 2 + ( n − e v e n ) ∗ e v e n ; ans = (even * even - even) / 2 + (n - even) * even; 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 << "\n";
}
/*
1 1 2 3 5 8 13 21 34
1 1 2 1 1 2 1 1 2
*/