【CodeForces 627A】XOR Equation

链接:

洛谷

博客园

题目大意:

两个正整数 (b)(c) 的和为 (s),它们的按位异或和为 (x)。请计算出所有可能的有序数对 ((b,c)) 的个数。

(2leq x,sleq10^{12})

正文:

因为 (b+c=2(bland c)+(boplus c)),所以有了 (s,x) 我们可以算出两个数的与值 (a=frac{s-x}{2})

如果不存在合法方案,就是上面的流程除了问题:

  1. 如果 (s<x)(a) 肯定就是负数了,这种情况肯定不合法。
  2. 如果 (2 mid(s-x))(a) 就不是整数,这种情况也不合法。
  3. 如果 (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;
}
原文地址:https://www.cnblogs.com/GJY-JURUO/p/14518315.html