P9825 [ICPC2020 Shanghai R] Fibonacci 题解

RP_I_AK_CSP · 2023-11-05 21:00:28 · 题解

P9825 [ICPC2020 Shanghai R] Fibonacci 题解

大致思路：

斐波那契数列有奇偶性的规律：奇、奇、偶、奇、奇、偶……

总共偶数个数为 x = n ÷ 3 个，而想要使乘积是偶数，只有奇数乘偶数或偶数乘偶数两种可能：

• 第一种奇数乘偶数。贡献值为 x (n - x)。

• 第二种偶数乘偶数。贡献值为 x (x - 1) ÷ 2。

把它们相加就是总贡献值。

正确代码：

#include<bits/stdc++.h>
using namespace std;
long long n,x,a,b;
int main(){
    cin>>n;
    x=n/3;
    a=x*(n-x);
    b=x*(x-1)/2;
    cout<<(a+b)<<endl;
    return 0;
}

这道题就这样完成啦！！！