CF1790E Vlad and a Pair of Numbers 题解

题目

链接

https://www.luogu.com.cn/problem/CF1790E

字面描述

题面翻译

共有 $t$ 组数据。

每组数据你会得到一个正整数 $x$，你需要构造一组正整数 $a$ 和 $b$，满足：

• $a+b=x\times 2$；

• $a\mathrm{xor}b=x$，其中 $\mathrm{xor}$ 指异或。

输出你构造的 $a$ 和 $b$。如有多解，任意输出一解即可。如无解，输出 $-1$。

$1\le t\le 10^4$，$1\le x\le 2^{29}$。同时，你需要保证你构造的 $a$，$b$ 满足 $1\le a,b\le 2^{30}$。

题目描述

Vlad found two positive numbers $ a $ and $ b $ ( $ a,b>0 $ ). He discovered that $ a \oplus b = \frac{a + b}{2} $ , where $ \oplus $ means the bitwise exclusive OR , and division is performed without rounding…

Since it is easier to remember one number than two, Vlad remembered only $ a\oplus b $ , let’s denote this number as $ x $ . Help him find any suitable $ a $ and $ b $ or tell him that they do not exist.

输入格式

The first line of the input data contains the single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases in the test.

Each test case is described by a single integer $ x $ ( $ 1 \le x \le 2^{29} $ ) — the number that Vlad remembered.

输出格式

Output $ t $ lines, each of which is the answer to the corresponding test case. As the answer, output $ a $ and $ b $ ( $ 0 < a,b \le 2^{32} $ ), such that $ x = a \oplus b = \frac{a + b}{2} $ . If there are several answers, output any of them. If there are no matching pairs, output -1.

样例 #1

样例输入 #1

6
2
5
10
6
18
36

样例输出 #1

3 1
-1
13 7
-1
25 11
50 22

思路

根据题目 $a+b=2x和a$ $xor$ $b=x$

我们能发现一个非常高重要的突破点$a异或b流失了x$
∴$a按位与b=x/2$
∵题目可输出任意解
∴$a=x/2,b=x+x/2$

但我们还要考虑一个无解的情况：
当x是奇数时，无法被2整除，无解
当$(x/2)按位与x!=0$，有误，无解

OK，过程理完，上代码

代码实现

#include<bits/stdc++.h>
using namespace std;int t,n; 
int main(){scanf("%d",&t);while(t--){scanf("%d",&n);if(n%2==1){printf("-1\n");continue;}if(((n/2)&n)!=0){printf("-1\n");continue;}printf("%d %d\n",n/2,n/2+n);}return 0;
}