链接:
题目大意:
两个正整数 (b) 和 (c) 的和为 (s),它们的按位异或和为 (x)。请计算出所有可能的有序数对 ((b,c)) 的个数。
(2leq x,sleq10^{12})。
正文:
因为 (b+c=2(bland c)+(boplus c)),所以有了 (s,x) 我们可以算出两个数的与值 (a=frac{s-x}{2})。
如果不存在合法方案,就是上面的流程除了问题:
- 如果 (s<x),(a) 肯定就是负数了,这种情况肯定不合法。
- 如果 (2 mid(s-x)),(a) 就不是整数,这种情况也不合法。
- 如果 (aland x eq0),两个数的与值的二进制的第 (i) 位是两者二进制第 (i) 位都等于 (1) 是等于 (1) 否则为 (0)。而异或值二进制第 (i) 位在两者二进制第 (i) 位都等于 (1) 时肯定为 (0),所以 (aland x) 肯定为 (0)。如果不为零,这种情况也不合法。
接下来如果 (x_i=1),那么 (b_i,c_i) 都有 (0,1) 两种情况故答案乘二,否则只有 (b_i=c_i=1) 的情况。另外如果 (a=0),还需要特判 (b=c=0,c=b=0) 的两种情况。
代码:
ll s, x;
ll ans;
int main()
{
scanf ("%lld%lld", &s, &x);
ll a = (s - x) / 2, cnt = 0;
if ((s - x) % 2 || (a & x) || x > s) {puts("0"); return 0;}
for (; x; cnt += x % 2, x >>= 1);
ans = (1ll << cnt) - (a? 0: 2);
printf("%lld
", ans);
return 0;
}