Codeforces 76D 位运算

题意:给你两个数x 和 y, x = a + b, y = a XOR b,问有没有合法的a和b满足这个等式?

思路:有恒等式: a + b = ((a & b) << 1) + (a ^ b),所以x - y = ((a & b) << 1), 如果x - y奇数,那就没有合法方案,否则我们可以构造出来.相当于已知a ^ b和a & b, 可以构造一组解了。

代码:

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
int main() {
ull x, y, z;
ull ans1 = 0, ans2 = 0;
scanf("%llu%llu", &x, &y);
z = x - y;
if(z & 1) printf("-1\n");
else {
z >>= 1;
for (int i = 0; i < 64; i++) {
if(((z >> i) & 1) == 1) {
ans1 |= (1llu << i);
ans2 |= (1llu << i);
} else {
if(((y >> i) & 1) == 1)
ans2 |= (1llu << i);
}
}
printf("%llu %llu\n", ans1, ans2);
}
}

  

上一篇:maven项目更换本地仓库


下一篇:Codeforces 868D Huge Strings - 位运算 - 暴力