题解 CF76D 【Plus and xor】

· · 题解

题解 CF76D

这是一道不错的位运算性质题。

我们先来了解几个柿子（可以下去自己推推看）：

（此处\operatorname{and}为按位与，\operatorname{or}为按位或，\operatorname{xor}为按位异或）

$a+b=a\operatorname{or}b+a\operatorname{and}b=a\operatorname{xor}b+2\times (a\operatorname{and}b)$ （2） ------------ 我们发现，题目中告诉了我们 $x+y$ 和 $x\operatorname{xor}y$ 的值 那么自然而然地， $x\operatorname{and}y$ 的值就是可求并且是固定的了 考虑在 $x+y$ 中，要使 $x$ 的值最小，就让 $x$ 在 $x\operatorname{and}y$ 中的“贡献”尽量少 对于 $x\operatorname{and}y$ 的每一位，若当前位位 $1$ ，则 $x,y$ 的对应位上的值都必须为 $1$ ，否则就让 $x$ 的为 $0$ ， $y$ 的为 $1$（因为$x$要尽量小）。 所以 $\min x=x\operatorname{and}y

那么 y=x+y-(x\operatorname{and}y)

那什么时候无解呢？

考虑公式（2），因为 a\operatorname{and}b 的值为正整数，所以如果 A-B 为奇数则无解

同样，A<B 时也无解

\text{\color{Red}注意数据范围！！！！！}

代码奉上

unsigned long long a, b, d;
signed main() {
   cin >> a >> b;
   d = a - b;
   if(d < 0 || d & 1) puts("-1");
   else {
       cout << d / 2 << ' ' << a - (d / 2);
   }
   return 0;
}