CF1790E题解

· · 题解

CF1790E 题解

传送门

题目大意

给定 t 个正整数 x，构造一组正整数 a 和 b，使得 a + b = x \times 2 且 a \operatorname{xor} b = x。若有多组解，输出任意一组解；若无解，输出 -1。

需要注意的是，这里 a 和 b 都需要是正整数，并且并没有要求 a \neq b，也就是说 a 和 b 可以相等。

解题思路

我们对 a \oplus b = x 进行转换，得到：

\begin{aligned} a \oplus b = x & \Leftrightarrow a = x \oplus b \\ & \Leftrightarrow a = (x \oplus (2x - a)) \\ & \Leftrightarrow a = 3x / 2 \oplus a \end{aligned}

两边同时异或上 a，则得到：

\begin{aligned} a \oplus a \oplus a &= a \oplus (3x / 2) \\ 0 \oplus a \oplus a &= 3x/2 \\ a &= 3x/2 \end{aligned}

所以只用判断 \frac{3}{2}x \oplus \frac{1}{2}x 是否等于 x 就行了。

代码如下：

#include <iostream>
using namespace std;
int main() {
    int t;
    cin >> t; // 读入测试数据组数
    while (t--) { // 处理每一组测试数据
        int x;
        cin >> x; // 读入正整数 x
        long long a = x / 2, b = x + (x - a); // 根据题目意思求出满足条件的 a 和 b
        if ((a ^ b) == x) // 如果异或结果与 x 相等，则说明 a 和 b 满足条件
            cout << a << ' ' << b << '\n'; // 输出 a 和 b
        else
            cout << "-1\n"; // 否则输出 -1
    }
    return 0;
}