C++题解:CSP迎国庆热身公益赛T1——位运算

题⽬描述

给定 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;
    }
}
上一篇:Solution Of 不会输的游戏


下一篇:10.2 国庆集训测试