【Comet OJ - Contest #4】B.奇偶性

「爱情、让人受尽委屈。」 2022-01-27 04:07 183阅读 0赞

题目链接：[奇偶性][Link 1]

### 题意： ###

输入![l][]、![r][]、![k][]根据公式 ![20190525085331258.png][] 求出 ![2019052508542527.png][]。

### 思路： ###

由于![f\_\{n\}][f_n]是对2取模，因此，我们可以知道每个数的值只有2种可能，1或0，如果![f\_\{i\}][f_i]是奇数，值就为1，如果是偶数，值就为0，所以我们只用判断![l][]到![r][]一共有多少奇数即可；

从公式中我们可以看出![i\\geqslant k][i_geqslant k]后面的数![f\_\{i\}][f_i]是前k个数的和，即![f\_\{i\}=f\_\{i-1\}+f\_\{i-2\}+\\cdots +f\_\{i-k\}][f_i_f_i-1_f_i-2_cdots _f_i-k]，而数学中我们知道n个数相加，如果奇数的个数是奇数，则结果一定是奇数；

由于输入中还含有k，因此我们猜想，奇数的个数可能与k也有关系，于是模拟出![k=2,3,4,5][k_2_3_4_5]的情况继续观察，如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTgxNzcy_size_16_color_FFFFFF_t_70][]

可以发现如果k是奇数，则所有的数都是奇数，答案就是![r-l+1][r-l_1]；如果k是偶数的话，只用判断![l][]到![r][]有多少偶数即可，下面可以结合代码看看

### My Code： ###

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<string>
    #include<algorithm>
    #include<queue>
    #include<math.h>
    #include<set>
    using namespace std;
    #define INF 1e9
    typedef long long ll;
    #define PI acos(-1)
    
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            ll l,r,k;
            scanf("%lld%lld%lld",&l,&r,&k);
            if(k %2 != 0) printf("%lld\n",r-l+1);
            else
            {
                ll x = r/(k+1);///判断r的左边有多少偶数
                ll y = l/(k+1);///判断l的左边有多少偶数
                if(r%(k+1) == k) x++;///判断第r个数是否为偶数
                if(l%(k+1) == k) y++;///判断第l个数是否为偶数
                ll ans = (r-x)-(l-1-y);
                printf("%lld\n",ans);
            }
    
        }
        return 0;
    }

[Link 1]: https://www.cometoj.com/contest/39/problem/B?problem_id=1577
[l]: https://private.codecogs.com/gif.latex?l
[r]: https://private.codecogs.com/gif.latex?r
[k]: https://private.codecogs.com/gif.latex?k
[20190525085331258.png]: https://img-blog.csdnimg.cn/20190525085331258.png
[2019052508542527.png]: /images/20220127/316b5fffb12e457fb19b5aeb8ec0e91d.png
[f_n]: https://private.codecogs.com/gif.latex?f_%7Bn%7D
[f_i]: https://private.codecogs.com/gif.latex?f_%7Bi%7D
[i_geqslant k]: https://private.codecogs.com/gif.latex?i%5Cgeqslant%20k
[f_i_f_i-1_f_i-2_cdots _f_i-k]: https://private.codecogs.com/gif.latex?f_%7Bi%7D%3Df_%7Bi-1%7D&plus;f_%7Bi-2%7D&plus;%5Ccdots%20&plus;f_%7Bi-k%7D
[k_2_3_4_5]: https://private.codecogs.com/gif.latex?k%3D2%2C3%2C4%2C5
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTgxNzcy_size_16_color_FFFFFF_t_70]: /images/20220127/2df4a32221ce4f7e92e60c69a7477329.png
[r-l_1]: https://private.codecogs.com/gif.latex?r-l&plus;1