CF1790E Vlad and a Pair of Numbers 题解
题目链接字面描述题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 思路代码实现题目
链接
/problem/CF1790E
字面描述
题面翻译
共有 t t t 组数据。
每组数据你会得到一个正整数 x x x，你需要构造一组正整数 a a a 和 b b b，满足：
a + b = x × 2 a + b = x \times 2 a+b=x×2；
a xor b = x a \operatorname{xor} b = x axorb=x，其中 xor \operatorname{xor} xor 指异或。
输出你构造的 a a a 和 b b b。如有多解，任意输出一解即可。如无解，输出 − 1 -1 −1。
1 ≤ t ≤ 1 0 4 1 \leq t \leq 10^4 1≤t≤104， 1 ≤ x ≤ 2 29 1 \leq x \leq 2^{29} 1≤x≤229。同时，你需要保证你构造的 a a a， b b b 满足 1 ≤ a , b ≤ 2 30 1 \leq a,b \leq 2^{30} 1≤a,b≤230。
题目描述
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
6251061836
样例输出 #1
3 1-113 7-125 1150 22
思路
根据题目 a + b = 2 x 和 a a+b=2x和a a+b=2x和a x o r xor xor b = x b=x b=x
我们能发现一个非常高重要的突破点 a 异或 b 流失了 x a异或b流失了x a异或b流失了x
∴ a 按位与 b = x / 2 a按位与b=x/2 a按位与b=x/2
∵题目可输出任意解
∴ a = x / 2 , b = x + x / 2 a=x/2,b=x+x/2 a=x/2,b=x+x/2
但我们还要考虑一个无解的情况：
当x是奇数时，无法被2整除，无解
当 ( x / 2 ) 按位与 x ! = 0 (x/2)按位与x!=0 (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;}
