求两个整数之间偶数奇偶数的个数

Question

我想求两个整数之间的偶数奇偶数的个数。以下是我目前所写的内容：

#include <bits/stdc++++.h>
using namespace std;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL)
#define ll long long int

bool findParity(ll x)
{
    ll y = x ^ (x >> 1);
    y = y ^ (y >> 2);
    y = y ^ (y >> 4);
    y = y ^ (y >> 8);
    y = y ^ (y >> 16);

    if (y & 1)
        return 1;
    return 0;
}

void solve()
{
    ll a,b; cin >> a >> b;
    ll evenparity = 0;
    for(ll i = a; i <= b; ++i){
        if(findParity(i)==0) evenparity++;
    }
    cout << evenparity;
}

signed main()
{
    fastio;
    solve();
    return 0;
}

这个很管用。但是，A和B这两个整数之间的差值可能高达10^11，这意味着类似这样的O(n)解决方案是行不通的。是否有一个更有效的，即O(1)解决方案来解决这个问题？

Answer 1

你所需要的是一个函数，它从[0-x]区间计算偶数奇偶校验数，我们称之为sumParity，然后简单地返回sumParity(b)-sumParity(a-1)。（如果我理解得正确的话，你要找的是[a,b]闭区间。）

如果从零开始对奇偶校验进行计数，并将数字(0-1)、(2，3)、(4，5)配对，则每对中正好有1个偶数和1个奇数奇偶校验。（这些对仅在最低位不同）。

因此，如果x是奇数，则sumParity(x)=(x+1)/2，否则x/2+parity(x)。

（您已经具有奇偶校验(x)函数）

f（a,b）=总和奇偶校验（b）-总和奇偶校验（a-1）

它只适用于正整数，但您也可以很容易地将逻辑扩展到负数。

Answer 2

每对偶数/奇数整数正好包含一个偶数奇偶数。

因此，只要检查a和b是否为偶数奇偶数，看看它们是否对自己的偶数/奇数对有贡献，并计算中间对就足够了。这是O(1)。