当前位置：网站首页>2020 ICPC Shanghai Site G

2020 ICPC Shanghai Site G

2022-08-10 19:07:00 【eyuhaobanga】

G. Fibonacci
可知x·y为偶数，那么x和y的组成要么是一奇一偶要么是两个偶数，所以通过观察Fibonacci数列可以得到，每三个作为一个循环，每个循环前两个为奇数，第三个为偶数，因此偶数的个数就是 $\left \lfloor \frac{n}{3} \right \rfloor$ ，奇数的个数就是 $n-\left \lfloor \frac{n}{3} \right \rfloor$ ，因此奇数和偶数互相匹配的个数就是 $\left \lfloor \frac{n}{3} \right \rfloor*\left ( n-\left \lfloor \frac{n}{3} \right \rfloor \right )$ ，偶数匹配偶数可以得到一个等差数列，根据等差数列求和公式得到 $\frac{\left \lfloor \frac{n}{3} \right \rfloor *\left ( \left \lfloor \frac{n}{3} \right \rfloor - 1\right )}{2}$
AC代码：
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;
using LL = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int cnt = n / 3;
    LL ans = 1ll * cnt * (n - cnt) + 1ll * (cnt - 1) * cnt / 2;
    cout << ans << '\n';

    return 0;
}