统计区间内奇数与偶数的数量｜数学归纳法

第二题 - 统计区间内奇数与偶数的数量

题目链接跳转：点击跳转

对于这种区间的问题，可以先考虑一部分。如果要求出从 $[1, L]$ 区间内满足条件的数字我们应该怎么办？假设 $L$ 是一个偶数，那么 $[1, L]$ 区间的奇数和偶数就应该是 $L / 2$。相同地，假设 $L$ 是一个奇数，那么 $[1, L]$ 区间的奇数和偶数就分别是 $L / 2 + 1$ 和 $L / 2$。注意到 $L / 2 + 1$ 和 $L / 2$ 两个公式都可以被简写成 $(L + 1) / 2$。

设 $odd(L)$ 和 $even(L)$ 分别为区间 $[1, L]$ 的奇数个数和偶数个数。那么可以得出结论，如果要求 $[L, R]$ 区间的奇数个数，答案就应该是 $odd(R) - odd(L-1)$ 和 $even(R) - even(L-1)$。

本题的 AC 代码如下，代码并没有使用函数，见谅：

#include <iostream>
using namespace std;

/*
思维水题。
稍微想一下找找规律就好了。
*/

int q, l, r, k;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> q;
    while(q--){
        cin >> k >> l >> r;
        if (k == 1) cout << ((r + 1) >> 1) - ((l) >> 1) << endl;
        else cout << (r >> 1) - ((l - 1) >> 1) << endl;
    }
    return 0;
}