题解 CF76D 【Plus and xor】

· · 题解

CF的思维题，本蒟蒻做了很久，题解没一个看懂的，好不容易A了，自己发一篇吧

这种题肯定要搞二进制吧。

假设我们分别模拟二进制下的加法和乘法。

0+0=0,0xor0=0 0+1=1,0xor1=1 1+1=10,1xor1=0

也就是说，只有二进制位刚好都为1是，异或值和加法值才能不一样。

这个值差了2的次方倍，其他情况下，加法和异或值都相等。

我们很容易算出加法和异或结果的差，也就是A-B。

也就是说，假如有k位二进制位均为1，那么A-B=2^k

这一差值是由多个相同位置二进制均为1的数对贡献的。

那么怎么求X和Y的值呢？这就是下一个问题了。

我们不如先去考虑什么时候无解吧

接下来考虑什么时候不成立吧。

很显然，我们的差值需要由A-B贡献，那A-B必须大于0。

由于2^k=A-B，所以A-B必须整除2

回到刚才的问题

我们可以推导一下，我们要求最小的X，最小的X一定是二进制均为1的最高位。举个例子：

1111011xor0011011$,那么我们能取的就是二者二进制均为$1$的最高位，也就是公共位即$11011$，此时剩下的位数就可以放在Y的位置。$A-B$显然是二的倍数，表示为2进制就是$100...00$(k个0).而最高位公共$1$位只有$01,11$这样的情况才能通过异或贡献出二的倍数，此时最小的公共部分肯定是左移一位的结果，即$a-b>>1

代码：

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
signed main()
{
    int a,b;
    cin>>a>>b;
    if((a-b)&1ull||a-b<0)
    puts("-1");
    else
    cout<<((a-b)>>1ull)<<" "<<(a-((a-b)>>1ull));
    return 0;
}