P9825

Xdwjs · 2023-11-05 20:17:15 · 题解

题目要求我们输出积为偶数时 i 和 j 的组合方式数量。

观察斐波那契数列。前两个数都是奇数，所以第三个数就是偶数；前两个数一个奇数一个偶数，所以第四个数就是奇数；前两个数一个奇数一个偶数，所以第五个数也是奇数。

以此类推。我们很容易发现，如果将斐波那契数列三个分为一组，则每组的前两个数是奇数，最后一个数是偶数。

下一步需要另一个规律：一个偶数乘上另一个数，结果还是偶数，只有相乘的两个数都为奇数时，结果才是奇数。

于是思路就有了，先算出数列中奇数的个数，求出这么多数的组合方式数量，这就是积为奇数时 i 和 j 的组合方式数量，再用所有 i 和 j 的组合数量减去积为奇数时的组合方式数量，就是积为偶数时的组合方式数量。

Code：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int o=(n/3*2)+(n%3);//表示奇数的个数
    cout<<n*(n-1)/2-o*(o-1)/2;
    return 0;
}