题⽬描述
给定 3个正整数 a , b , c a, b, c a,b,c。请求出三个正整数 ,满足:
u + v = a u + v=a u+v=a
u − v = b u - v=b u−v=b
u ⊕ v ⊕ w = a ⊕ b ⊕ c u \oplus v \oplus w= a \oplus b \oplus c u⊕v⊕w=a⊕b⊕c
其中
⊕
\oplus
⊕表示逻辑异或运算,在 c++ 中可以通过 a ^ b
得到 a 异或 b 的值。
如果不存在,请输出 -1。可以证明,最多只有⼀组满⾜条件的 。
输入描述
本题有多组测试数据。
第⼀⾏⼀个整数
T
T
T,表⽰数据组数。
接下来
T
T
T行, 每行3个正整数
a
,
b
,
c
a, b, c
a,b,c。
输出描述
T
T
T行,每行输出三个正整数 或者输出 -1 表⽰⽆解。
输入样例
3
7 5 10
20 6 12
10 12 10
输出样例
6 1 15
13 7 20
-1
样例解释
对于样例:
- 6 + 1 = 7 , 6 − 1 = 5 6+1=7,6-1=5 6+1=7,6−1=5, 6 ⊕ 1 ⊕ 15 = 7 − ⊕ 5 ⊕ 10 6 \oplus 1 \oplus 15= 7 - \oplus 5 \oplus 10 6⊕1⊕15=7−⊕5⊕10,
- 13 + 7 = 20 , 13 − 7 = 6 13+7=20,13-7=6 13+7=20,13−7=6, 13 ⊕ 7 ⊕ 20 = 20 ⊕ 6 ⊕ 12 13 \oplus 7 \oplus 20= 20 \oplus 6 \oplus 12 13⊕7⊕20=20⊕6⊕12
- 可以证明第三组数据不存在正整数解。
数据范围
对于30%的数据,
1
≤
a
,
b
,
c
≤
1
0
2
1\le a,b,c\le10^2
1≤a,b,c≤102
对于60%的数据,
1
≤
a
,
b
,
c
≤
1
0
9
1\le a,b,c\le10^9
1≤a,b,c≤109
对于100%的数据,
1
≤
a
,
b
,
c
≤
1
0
18
,
1
≤
T
≤
1
0
3
1\le a,b,c\le10^{18}, 1\le T \le10^3
1≤a,b,c≤1018,1≤T≤103
算法思想(模拟)
根据题目描述:
u + v = a u + v=a u+v=a
u − v = b u - v=b u−v=b
得 u = a + b 2 , v = a − b 2 u = \frac{a + b}{2},v = \frac{a - b}{2} u=2a+b,v=2a−b,因此可知:当 a + b a+b a+b为奇数,或者 a ≤ b a\le b a≤b时无解。
最后,由于 u ⊕ v ⊕ w = a ⊕ b ⊕ c u \oplus v \oplus w= a \oplus b \oplus c u⊕v⊕w=a⊕b⊕c,根据异或性质:
a ⊕ a = 0 a \oplus a = 0 a⊕a=0
a ⊕ b ⊕ c ⊕ u ⊕ v ⊕ w = 0 a \oplus b \oplus c \oplus u \oplus v \oplus w = 0 a⊕b⊕c⊕u⊕v⊕w=0,那么 w = a ⊕ b ⊕ c ⊕ u ⊕ v w = a \oplus b \oplus c \oplus u \oplus v w=a⊕b⊕c⊕u⊕v。
注意:
代码实现
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int main()
{
int T;
cin >> T;
while(T --)
{
LL a, b, c;
cin >> a >> b >> c;
if((a + b) % 2 || a <= b)
{
cout << -1 << endl;
continue;
}
LL u = (a + b) / 2, v = (a - b) / 2, w;
w = a ^ b ^ c ^ u ^ v;
if(w <= 0) cout << -1 << endl;
else cout << u << " " << v << " " << w << endl;
}
}