CF1245F:清理春天的数学挑战

CF1245F: 清理春天的数学挑战

题目描述:

本题涉及一个数学挑战，给定一个区间 [L, R]，其中 0 ≤ L, R ≤ 10^9。任务是在这个区间内找到所有满足 x + y = x ∧ y 的数对 (x, y)，并计算这些数对的总数。

输入说明：

• 首行输入一个整数 T，表示测试用例的数量。


• 接下来 T 行，每行包含两个整数 L 和 R，代表区间的起始和结束位置。

输出说明：

• 对于每个测试用例，输出一行，包含一个整数，即满足条件的数对总数。

解题思路：

关键在于理解等式 x + y = x ∧ y 的含义，这实际上意味着 x 和 y 在二进制表示中没有相同的 1 位，即 x ∧ y = 0。因此，问题转化为寻找区间内 x ∧ y = 0 的数对。

为了高效解决这个问题，我们定义了几个辅助函数来帮助计算：

• f(l, r): 表示区间 [l, r) 内满足条件的数对数量。


• g(x, n): 表示在 0 到 n 范围内，与 x 进行按位与运算结果为 0 的数 y 的数量。


• h(x, n): 表示在 n - lowbit(n) 到 n 范围内，与 x 进行按位与运算结果为 0 的数 y 的数量。

通过递归地将区间缩小，并利用上述函数，可以有效地计算出最终结果。特别是当 l 或 r 为奇数时，需要特殊处理，确保计算的准确性。

代码实现：

#include
using namespace std;
typedef long long ll;

ll g(int a, int b)
{
    ll res = 0;
    ll num = 0;

    for(int i = 1; i <= b; i <<= 1)
    {
        if(b & i)
        {
            b ^= i;
            if(!(a&b)) res += 1<        }
        if(!(a&i)) num++;
    }

    return res;
}

ll calc(int a, int b)
{
    if(a == b) return 0;
    if(a == 0) return 2*b - 1 + calc(1, b);
    ll res = 0;
    if(a & 1)
    {
        // f(l,r)=f(l+1,r)+2(g(l,r)-g(l,l))
        res += 2 * (g(a, b) - g(a,a));
        a++;
    }
    if(b & 1)
    {
        // f(l,r)=f(l,r-1)+2(g(r-1,r)-g(r-1,l))
        res += 2 * (g(b-1, b) - g(b-1, a));
        b--;
    }
    return res + 3 * calc(a/2, b/2);
}

int main()
{
    int T; cin >> T;
    int a, b;
    while(T--)
    {
        cin >> a >> b;
        cout <    }
    return 0;
}