题解：CF1790E Vlad and a Pair of Numbers

I_do_Cpp · 2026-04-20 19:59:30 · 题解

前置知识

二进制运算

题目解析

文章中，\oplus 表示按位异或，\& 表示按位与，\ll 表示左移，若无特殊说明，位代表二进制位。

考虑如何用位运算实现加法。

给出一个公式。

解释这个公式。显然 a \oplus b 是 a+b 不进位的结果（可以自己对应一下），a \& b 是每一位是否进位（只有都是 1 才进位，对应的位也才是 1），左移是因为进位是给前一位进的。

根据原题，因为是向下取整，显然 a+b-x 可能是 x 或 x+1，又因为这个数位 ((a \& b)\ll 1)，所以必然是 2 的倍数，结果唯一。我们把这个数右移得到了 a \& b，这样我们确定了 a \& b 的值。注意到对于每一位，若与的结果是 1，则异或的结果必然是 0，且 a,b 这一位都是 1，否则异或值随意，因为 0 和 1 都可以在 a,b 这一位不同时为 1 的前提下构造。

这里讲述一种简单判断方法，显然只有异或结果和与结果有至少一位同时为 1 才不合理，所以可以直接将这两个数按位与，若大于 1 则无解。

接下来构造数据。构造其实很简单，这里讲述一种最快的方法。我们说 a,b 需要满足：a \& b 中每一位是 1 的位，a,b 两数都应为 1，否则根据异或结果调整 a,b。显然 a 可以为 a\&b。因为 a \& b 中每一位是 1 的位，a 必然为 1，对于其他位 0，你无论每一位是 0 还是 1 都可以通过 b 的构造出来。

然后推导 b。

因为 x=a \oplus b，得 x \oplus a=a \oplus b \oplus a=b，所以 b=x \oplus a。

做完了。

正解代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int x;
        cin>>x;
        int andx=(x+(x%2))>>1;//这里加上 x%2的余数就一定是 2的倍数了。
        if((andx&x)>=1)
        {
            cout<<"-1\n";
            continue;
        }
        cout<<andx<<" "<<(x^andx)<<"\n";
    }
    return 0;
}